题意：给出一个数S，求约数和等于S的数。
这是一道数学题，深搜只是个幌子，如果是纯代码的话，会非常难读，所以我写一份比较详细的题解，但恐怕还是不能把这道题的美妙写尽，罢了，数学的精彩是需要有心人领会的，可惜我没心；
在解决这道题之前，在数学上需要储备两项知识：
1.算数基本定理：任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=P₁^a₁ P₂^a₂…Pn^an，这里P₁<P₂<…<Pn均为质数，其诸指数ai是正整数。
2.约数和定理：对于任意一个大于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)。
建议上网搜或者翻课本来加深对这两个知识的理解；
题中涉及了筛素数，所以建议大家掌握筛法的优化，这里不多解释，网上写的很多，也足够清楚；
接下来咱们马上看整个程序最核心的思想，我们学了约数和定理，是用来求原数的约数和的，但是这道题是给了一个约数和，让我们找所有可能的原数，所以不免会用到枚举，我们可以从这个式子入手：
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)。
我们可以看到，p1p2这样的素数我们可以递增去枚举，对于指数a可以用循环判断来做到，当我们确定了一组可行的因式时（形如(P₁^0+P₁^1+P₁^2+…P₁^a₁)），就可以把它从原式里除去，这就达到了拆分原数的目的；根据题意我们可以知道，我们把原式拆成1之后，就需要看我怎么得到我要的结果，我们仔细观察这个式子
拆完之后，
P₁^a₁*
P₂^a
₂*...*Pn^an
这就是我想得到的一组解，这个数的约数和就是原数！为什么呢？因为在原式中，
P₁^0、
P₁^1...
这些都是
P₁^a₁
的因式，以此类推，所以分解因式之后再加起来，就是我要的原数，这一点很神奇；
另外，我如果在搜索的时候，拆剩下的数减1是一个新的质数，那么就可以看成是Pn^0+Pn^1
这种形式，即是满足上面列的等式的，我只需要把以前拆出来的
P₁^a₁*
P₂^a
₂*...
等各项再乘给
P
n
^1
，依然会得到一个非常合法的结果，这样，这道题就算得以解决了，只是有些代码问题还非常谜，我会给出比较详细的注释的；
现在分享代码：
1 #include<iostream>
2 #include<cstdio>
3 #include<
string>
4 #include<cstring>
5 #include<cstdlib>
6 #include<cmath>
7 #include<algorithm>
8 #include<queue>
9 #include<stack>
10 #include<iterator>
11 using namespace std;
12 const int MAXN=
100010;
13 bool nop[MAXN];
int isp[MAXN];
14 long long ans[MAXN],sum,num,cnt=
0;
15 long long n,m;
16 void prime()
//筛素数；
17 {
18 nop[
0]=nop[
1]=
1;
19 for(
int i=
2;i<=MAXN;i++
){
20 if(!nop[i]) isp[++cnt]=
i;
21 for(
int j=
1;j<=cnt&&isp[j]*i<MAXN;j++
){
22 nop[isp[j]*i]=
true;
23 if(i%isp[j]==
0)
break;
24 }
25 }
26 }
27 bool pd(
long long x)
//判素数
28 {
29 if(x==
1)
return 0;
30 for(
int i=
1;isp[i]*isp[i]<=x;i++
){
31 if(x%isp[i]==
0)
return 0;
32 }
33 return 1;
34 }
35 void dfs(
long long now,
int k,
long long left)
//now是目前搜出的结果（形如pow(P1,a1)*pow(P2,a2)*...这样的式子），k是目前用到的素数，left是把原数拆分后剩余的部分；
36 {
37 if(left==
1){
//如果原式被拆完了，那就得出结果；
38 ans[++cnt]=
now;
39 return ;
40 }
41 if(left-
1>=isp[k]&&pd(left-
1)){
42 ans[++cnt]=(left-
1)*now;
//题解中补充的问题，望诸位理智吸收
43 }
44 for(
int i=k;isp[i]*isp[i]<=left;i++
){
45 for(
long long tmp=isp[i]+
1,tt=isp[i];tmp<=left;tt*=isp[i],tmp+=
tt){
46 if(left%tmp==
0){
//这是在拆分P和a，tt是用来完成乘方运算的，tmp是来完成各约数相加的；
47 dfs(tt*now,i+
1,left/tmp);
//"/tmp"是在拆式子，tmp是各种因式；
48 }
49 }
50 }
51 return ;
52 }
53 int main()
54 {
55 prime();
56 while(~scanf(
"%lld",&
n)){
57 memset(ans,
0,
sizeof(ans));
58 cnt=
0;
59 dfs(
1,
1,n);
60 sort(ans+
1,ans+
1+
cnt);
61 printf(
"%lld\n",cnt);
62 for(
int i=
1;i<cnt;i++
){
63 printf(
"%lld ",ans[i]);
64 }
65 if(cnt)
66 printf(
"%lld\n",ans[cnt]);
67 }
68 return 0;
69 }
View Code
转载于:https://www.cnblogs.com/Alan-Luo/articles/8721328.html
相关资源：BZOJ题目镜像
