@OceanEye7年前
04/11
23:03
莫比乌斯反演
普通的莫比乌斯反演就是搞出一个分式然后利用[n/i]的连续性制造根号复杂度的东西啊= =
这里的推导也是一样的
先找到simple的f(x) & g(x)
f(x)=sigma(i)sigma(j) gcd(i,j)==x
g(x)=sigma(i)sigma(j) x|gcd(i,j)
上面这个东西随便反演吧= =然后把所有的质数尝试带进x里面
sigma(prime -> p) f(x) == sigma(prime -> p) sigma(dx<=p) g(dx) * μ(d)
把dx换成C,会发现一个C对应着几个 μ(d),这里是一个质因子对应一个 μ(d)。
这里把上面那行东西的值想成一个奇奇gaygay的数论函数h(C)就可以了。
【最神奇的是这个函数居然可以线性求= =太神了不仔细看都看不出来】
这里就可以对于1-N中的每个数来计算贡献了= =
即是 sigma(C = 1 to N) [N/C]*[M/C] * h(C)
然后套一套根号前缀和就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #define p(x) ('0'<=x&&x<='9') #define ll long long char cc; void read(int &x) { cc=getchar(); x=0; while(!p(cc)) cc=getchar(); while(p(cc)) { x=x*10+cc-48; cc=getchar(); } } using namespace std; #define M 10000000 int prime[M+10],miu[M+10],mn[M+10],tot; int g[M];//pre[]; bool isprime[M+10]; void pre() { miu[1]=1; for(int i=2;i<=M;i++) { if(!isprime[i]) { miu[i]=-1;g[i]=1; prime[tot++]=i; } for(int j=0,k;j<tot;j++) { k=i*prime[j]; if(k>M) break; isprime[k]=true; if(i%prime[j]==0) { miu[k]=0; g[k]=miu[i]; break; } miu[k]=-miu[i]; g[k]=miu[i]-g[i]; } } for(int i=1;i<=M;i++) g[i]+=g[i-1]; } int T,A,B; ll ans; int main() { pre(); for(read(T);T--;) { ans=0; read(A); read(B); if(A>B) swap(A,B); for(int node=1,m;node<=A;node=m+1) { m=min(A/(A/node),B/(B/node)); ans+=(ll)(g[m]-g[node-1])*(A/m)*(B/m); } printf("%lld\n",ans); } return 0; } |