题目: https://www.lydsy.com/JudgeOnline/problem.php?id=3629
如果要搜索, 肯定得质因数分解吧; 就应该朝这个方向想.
** 约数和定理:
对于任意一个大于 1 的正整数 N 可以分解正整数:
- N=
- P
- ?
- ^a
- ?
- P?^a?...Pn^an
, 则由约数个数定理可知 N 的正约数有
(a?+1)(a?+1)(a?+1)...(an+1)
个, 那么 N 的 (a?+1)(a?+1)(a?+1)...(an+1) 个正约数的和为 f(N)=(P?^0+P?^1+P?^2+...P?^a?)(P?^0+P
- ?^1+P
- ?^2+...P
- ?^a?)...(Pn^0+Pn^1+Pn^2+...Pn^an)
- .
知道这个就可以枚举质因数和它们的指数, 根据当前剩下的 S 进行 dfs 了.(唉, 我竟然都不知道)
- https://blog.csdn.net/eolv99/article/details/39644419
- https://blog.csdn.net/eolv99/article/details/39644419
代码是跟着这个写的 https://blog.csdn.net/PoPoQQQ/article/details/39152381 (其实都一样?)
现在看来好像也就是这样罢了? 自己还是经验不足(太蒟).
- (1e5?)
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define ll long long
- using namespace std;
- const int N=1e5+5,Mxn=2e9;
- int p[N],tot,ans[N],num;
- bool vis[N];
- void get_pri()
- {
- for(int i=2;i<=N;i++)//N is enough,not Mxn,or the array is not enough
- {
- if(!vis[i])p[++tot]=i;
- for(int j=1;j<=tot&&(ll)i*p[j]<=N;j++)
- {
- vis[i*p[j]]=1;
- if(i%p[j]==0)break;
- }
- }
- }
- bool is_pri(int n)
- {
- if(n==1)return false;//
- for(int i=1;p[i]*p[i]<=n;i++)
- if(n%p[i]==0)return false;
- return true;
- }
- void dfs(int now,int pos,int left)
- {
- if(left==1){ans[++num]=now;return;}
- if(is_pri(left-1)&&left-1>=p[pos])//>=,it> sqrt(left)
- ans[++num]=(left-1)*now; // 这是只含一个的大于 sqrt(left)的质数
- for(int i=pos;i<=tot&&(ll)p[i]*p[i]<=left;i++)// 其余质数有 2 个或以上
- {
- ll pwsum=p[i]+1,pw=p[i];
- for(;pwsum<=left;pw*=p[i],pwsum+=pw)//pwsum 是定理, pw 加到答案上
- if(left%pwsum==0)
- dfs(now*pw,i+1,left/pwsum);//i+1,not pos+1
- }
- }
- int main()
- {
- get_pri();int n;
- while(scanf("%d",&n)==1)
- {
- num=0;
- dfs(1,1,n);printf("%d\n",num);
- sort(ans+1,ans+num+1);
- for(int i=1;i<=num;i++)printf("%d%c",ans[i],i==num?'\n':' ');
- }
- return 0;
- }
bzoj 3629 [JLOI2014]聪明的燕姿 -- 约数和定理 + dfs
来源: http://www.bubuko.com/infodetail-2671509.html