bzoj 3629 [JLOI2014]聪明的燕姿——约数和定理+dfs

题目：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/PoPoQQQ/article/details/39152381（其实都一样？）

现在看来好像也就是这样罢了？自己还是经验不足（太蒟）。

（1e5？）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e5+,Mxn=2e9;

int p[N],tot,ans[N],num;

bool vis[N];

void get_pri()

{

  for(int i=;i<=N;i++)//N is enough,not Mxn,or the array is not enough

    {

      if(!vis[i])p[++tot]=i;

      for(int j=;j<=tot&&(ll)i*p[j]<=N;j++)

    {

      vis[i*p[j]]=;

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

    }

    }

}

bool is_pri(int n)

{

  if(n==)return false;//

  for(int i=;p[i]*p[i]<=n;i++)

    if(n%p[i]==)return false;

  return true;

}

void dfs(int now,int pos,int left)

{

  if(left==){ans[++num]=now;return;}

  if(is_pri(left-)&&left->=p[pos])//>=,it > sqrt(left)

    ans[++num]=(left-)*now;    //这是只含一个的大于sqrt(left)的质数

  for(int i=pos;i<=tot&&(ll)p[i]*p[i]<=left;i++)//其余质数有2个或以上

    {

      ll pwsum=p[i]+,pw=p[i];

      for(;pwsum<=left;pw*=p[i],pwsum+=pw)//pwsum是定理,pw加到答案上

    if(left%pwsum==)

      dfs(now*pw,i+,left/pwsum);//i+1,not pos+1

    }

}

int main()

{

  get_pri();int n;

  while(scanf("%d",&n)==)

    {

      num=;

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

      sort(ans+,ans+num+);

      for(int i=;i<=num;i++)printf("%d%c",ans[i],i==num?'\n':' ');

    }

  return ;

}