bzoj3629 [JLOI2014]聪明的燕姿——DFS+约数和定理

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3629

扫除了一个知识盲点：约数和定理

约数和定理：

对于一个大于1正整数n可以分解质因数：n=p1^a1*p2^a2*p3^a3*…*pk^ak,则由约数个数定理可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(ak+1)个，那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）

所以就可以搜索了，可是我搜索好蒻啊不会...

参考这篇博客：https://blog.csdn.net/eolv99/article/details/39644419

于是抄写了一下，但感觉还是没有领悟设计 dfs 的方法...

另外，输出那里注释掉的写法为什么一直WA明明我觉得没什么问题啊...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5;

int s,pri[maxn+],ans[maxn+],cnt,num;

bool vis[maxn+];

void init()

{

    vis[]=;

    for(int i=;i<=maxn;i++)

    {

        if(!vis[i])pri[++cnt]=i;

        for(int j=;j<=cnt&&i*pri[j]<=maxn;j++)

        {

            vis[i*pri[j]]=;

            if(i%pri[j]==)break;

        }

    }

}

bool ispri(int x)

{

    if(x<=maxn)return !vis[x];

//    for(int i=2;i*i<=x;i++)

//        if(x%i==0)return 0;

    for(int i=;pri[i]*pri[i]<=x;i++)

        if(x%pri[i]==)return ;

    return ;

}

void dfs(int last,int nw,int tot)

{

    if(tot==){ans[++num]=nw; return;}

    if(tot->pri[last]&&ispri(tot-))//tot-1>pri[last],否则可能之后被枚举到

    {

        ans[++num]=nw*(tot-); //此处不return

    }

    for(int i=last+;pri[i]*pri[i]<=tot;i++)

        for(int t=pri[i],ts=pri[i]+;ts<=tot;t*=pri[i],ts+=t)//+1是pri[i]^0

            if(tot%ts==)//!

                dfs(i,nw*t,tot/ts);

}

int main()

{

    init();

    while(~scanf("%d",&s))

    {

        num=;

        dfs(,,s);

        sort(ans+,ans+num+);

        printf("%d\n",num);

//        for(int i=1;i<num;i++)printf("%d ",ans[i]);

//        printf("%d\n",ans[num]);

        for(int i=;i<=num;i++)

        {

            printf("%d",ans[i]);

            if(i==num)printf("\n"); else printf(" ");

        }

    }

    return ;

}