[关闭]
@xzyxzy 2018-08-15T08:40:45.000000Z 字数 2838 阅读 542

[SDOI2015]约数个数和

题解


前言

首先感谢yyb的题解让我大概懂了做法
然后感谢syc的讲解让我明白的关键要点

正文

反演的题,从yyb那里看下大概流程,然后这里讲两个地方

Part 1 推式子


原理请见这篇文章章末引理

把外面的贡献提出来,那么每个会被枚举到次,同理计算

请自行反演,不会可以看yyb的博客,但最后一句写错了,是

解决后面这一坨


其实相当于这个(可以见刚才那篇文章的引理),用代替

然后运用乘法分配率

那么只需要对这个式子处理就好了

上式可以表示枚举一个因子,那么中有个数含有因子,枚举完中所有的因子然后累加,可以说是求中每个数的因子个数和吧,即

Part 2 线性筛

一个数唯一分解为,则


原理是枚举每个质因子选
我们可以知道一个数的约数个数函数是积性函数
所以可以线性筛,又和其他自定义的积性函数筛法略微不同
表示的因数个数,用表示唯一分解后最小质因子的次数
代码如下慢慢体会

  1. inline void Sieve()
  2. {
  3. ispri[1]=1;p[1]=1;d[1]=1;
  4. for(RG int i=2;i<=MAXN;i++)
  5. {
  6. if(!ispri[i]){pri[++tot]=i;p[i]=1;d[i]=2;}
  7. for(RG int j=1;j<=tot&&i*pri[j]<=MAXN;j++)
  8. {
  9. ispri[i*pri[j]]=1;
  10. if(i%pri[j]==0)
  11. {
  12. d[i*pri[j]]=d[i]/(p[i]+1)*(p[i]+2);//d[i]表示i的因数个数
  13. p[i*pri[j]]=p[i]+1;//p[i]表示i唯一分解后最小质因子的次数
  14. break;
  15. }
  16. d[i*pri[j]]=d[i]*d[pri[j]];//实际上就是d[i]*2
  17. p[i*pri[j]]=1;
  18. }
  19. }
  20. }

这样子预处理,处理询问,总复杂度

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #define RG register
  6. #define ll long long
  7. using namespace std;
  8. inline int read()
  9. {
  10. RG char ch=getchar();
  11. RG int h=0;
  12. while(ch>'9'||ch<'0')ch=getchar();
  13. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  14. return h;
  15. }
  16. const int MAXN=50000;
  17. int mu[MAXN+1],pri[MAXN>>1],tot;
  18. int p[MAXN+1],d[MAXN+1],s[MAXN+1],sd[MAXN+1];
  19. bool ispri[MAXN+1];
  20. inline void Mobius()
  21. {
  22. mu[1]=1;ispri[1]=1;p[1]=1;d[1]=1;
  23. for(RG int i=2;i<=MAXN;i++)
  24. {
  25. if(!ispri[i]){pri[++tot]=i;p[i]=1;mu[i]=-1;d[i]=2;}
  26. for(RG int j=1;j<=tot&&i*pri[j]<=MAXN;j++)
  27. {
  28. ispri[i*pri[j]]=1;
  29. if(i%pri[j]==0)
  30. {
  31. //mu[i*pri[j]]=0;//卡常
  32. d[i*pri[j]]=d[i]/(p[i]+1)*(p[i]+2);//d[i]表示i的因数个数
  33. p[i*pri[j]]=p[i]+1;//p[i]表示i唯一分解后最小质因子的次数
  34. break;
  35. }
  36. mu[i*pri[j]]=-mu[i];
  37. d[i*pri[j]]=d[i]*d[pri[j]];//实际上就是d[i]*2
  38. p[i*pri[j]]=1;
  39. }
  40. }
  41. for(RG int i=1;i<=MAXN;i++)s[i]=s[i-1]+mu[i];
  42. for(RG int i=1;i<=MAXN;i++)sd[i]=sd[i-1]+d[i];
  43. }
  44. int main()
  45. {
  46. RG int T=read();Mobius();
  47. while(T--)
  48. {
  49. RG int N=read(),M=read();
  50. if(N>M)swap(N,M);
  51. RG int l=1,r;RG ll ans=0;
  52. while(l<=N)
  53. {
  54. r=min(N/(N/l),M/(M/l));
  55. ans+=1LL*(s[r]-s[l-1])*sd[N/l]*sd[M/l];
  56. l=r+1;
  57. }
  58. printf("%lld\n",ans);
  59. }
  60. return 0;
  61. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注