bzoj3994: [SDOI2015]约数个数和(反演+结论?!)
程序员文章站
2022-04-09 11:29:08
这题做的历程堪称惊心动魄刚刚学了莫比乌斯反演的我高高兴兴的和cbx一起反演式子期间有突破,有停滞,有否定然后苟蒻的我背着cbx偷偷打开了题解看到了我。。。。。。去你的有个性质啊(当然还是自己知识储备不足) 具体证明(其实当时主要是想的方向偏了,不然这个定理自己也能想出来) 然后就可以愉快的反演了 Σ ......
这题做的历程堪称惊心动魄
刚刚学了莫比乌斯反演的我高高兴兴的和cbx一起反演式子
期间有突破,有停滞,有否定
然后苟蒻的我背着cbx偷偷打开了题解
看到了
我。。。。。。
去你的有个性质啊(当然还是自己知识储备不足)
具体证明
(其实当时主要是想的方向偏了,不然这个定理自己也能想出来)
然后就可以愉快的反演了
σ(i∈[1,n])σ(j∈[1.m])d(x,y)
=σ(i=1)σ(j=1)σ(x|i)σ(y|j)[gcd(x,y)==1]
=σ(i=1)σ(j=1)((n/i)*(m/j))σ(d|i&&d|j)μ(d)
=σ(d=1)μ(d)σ(i=1) (n/(d*i)) σ(j=1)(m/(d*j))
然后我们观察σ(n/(d*i))
根据性质 (n/(d*i))==((n/d)/i)
我们发现这个东西可以用数论分块o(sqrt(n))预处理,设为f[i]
则原式= σ(d=1)(μ(d)f[n/d]*f[m/d])
再用数论分块就好了
复杂度o(n*sqrt(n)+t*sqrt(n))
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #define ll long long 5 using namespace std; 6 int mu[50100],p[50010],top;ll tot[50100],f[50100];bool v[50010]; 7 int main(){ 8 f[1]=1;tot[1]=1; 9 for(int i=2;i<=50000;i++){ 10 if(!v[i]){ 11 p[++top]=i; 12 mu[i]=-1; 13 } 14 for(int j=1;j<=top&&i*p[j]<=50000;j++){ 15 if(!(i%p[j])){ 16 v[i*p[j]]=1; 17 break; 18 } 19 mu[i*p[j]]=-mu[i]; 20 v[i*p[j]]=1; 21 } 22 tot[i]=tot[i-1]+mu[i]; 23 int x; 24 for(int j=1;j<=i;j=x+1){ 25 x=(i/(i/j)); 26 f[i]+=(x-j+1)*(i/j); 27 } 28 } 29 int j,n,m,t;ll ans; 30 scanf("%d",&t); 31 while(t--){ 32 scanf("%d%d",&n,&m); 33 if(n>m) swap(n,m);ans=0; 34 for(int i=1;i<=n;i=j+1){ 35 j=min((n/(n/i)),(m/(m/i))); 36 ans+=(tot[j]-tot[i-1])*f[n/i]*f[m/i]; 37 } 38 printf("%lld\n",ans); 39 } 40 }