本文主要是介绍BZOJ 4803 逆欧拉函数 线性筛素数+dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
已知phi(N)，求N。
Input
两个正整数，分别表示phi(N)和K。
phi(N)<=10^14,K<=1000
Output
按升序输出满足条件的最小的K个N。
Sample Input
8 4
Sample Output
15 16 20 24
HINT
传送门
看上去很神……其实式子写写就基本出来了。
假设n=p1^a1*p2^a2*……*pk^ak，
那么：
φ(n)=n*∏(1-1/pi)
根据这个，又我们已经知道了φ(n)
所以n=φ(n)*∏(pi/(pi-1))
观察这个式子：
观察这个式子：
因为pi都是素数，所以(pi-1)和pi互质的，那么因为n是整数，
所以(pi-1)都是φ(n)的约数
而且(pi-1)的乘积也是φ(n)的约数。
那么有一个比较简单的想法就是枚举所有φ(n)的约数
然后一一弄，
显然看上去时间复杂度等等有点点不可做。
那么提供一种方法：
首先线性筛出10^7内的所有素数，也就是给出的φ(n)的根号
然后进入一个dfs暴力找所有n的过程，能够YY出满足某一个φ(n) n的个数不会很多，
（后面发现了<50W个）
对于当前的φ(n)，简便点用fi表示
那么首先当然是在所有筛出来的素数-1里面找有没有fi的约数，
如果有，假设它是x，那么除去fi里面的所有x，并且要求的n里面也得出现x，
暴力把x的个数累计上去做；
然后假如说fi>10^7，用Miller-Rabin判断(fi+1)是不是素数，
如果是，那么很明显直接得到了一个新的n；
就用这种方法不断取所有素数，具体过程用一个dfs实现。
考虑到时间等问题，素数的除去从大到小除去，那么会优化很多。
一开始各种地方写炸，还差点忘记miller-rabin怎么写……
竟然没什么题解……
后面发现一直WA的原因竟然是答案数组只开了1W……
暴力改了100W，然后又测了测50W都AC了。。
最重要的dfs的过程各种意义已经标注在代码里了，直接说有点说不清楚。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX=10000005,PrimeInMAX=650000,MR_Times=10;
int K,pcnt,anslen;
ll ans[500000],prime[PrimeInMAX];
bool notprime[MAX];
void Get_Prime(){notprime[1]=1,pcnt=0;for (int i=2;i<MAX;i++){if (!notprime[i]) prime[++pcnt]=i;for (int j=1;j<=pcnt;j++){if (prime[j]*i>=MAX) break;notprime[prime[j]*i]=1;if (!(i%prime[j])) break;}}
}
ll ksc(ll a,ll b,ll mod){ll x=0LL,t=a;while (b){if (b&1LL) x=(x+t)%mod;b>>=1LL;t=(t+t)%mod;}return x;
}
ll ksm(ll a,ll b,ll mod){ll x=1LL,t=a;while (b){if (b&1LL) x=ksc(x,t,mod);b>>=1LL;t=ksc(t,t,mod);}return x;
}
bool witness(ll a,ll n){ll j=0,t=n-1;while (!(t&1LL)) t>>=1LL,j++;ll tmp=ksm(a,t,n),last=tmp;while (j--){tmp=ksc(tmp,tmp,n);if (tmp==1LL && last!=1LL && last!=n-1) return 1;last=tmp;}if (tmp==1LL) return 1;return 0;
}
bool Miller_Rabin(ll n){if (n==2LL) return 1;if (n<=1LL || !(n&1LL)) return 0;for (int i=0;i<MR_Times;i++){ll a=rand()%(n-1)+1;if (!witness(a,n)) return 0;}return 1;
}
void solve(ll fi,ll n,int last){if (fi+1>prime[pcnt] && Miller_Rabin(fi+1))ans[++anslen]=n*(fi+1);
//当fi+1是一个素数，相当于一个素数-1=fi，直接得到新的nfor (int i=last;i;i--) //从大到小枚举约数if (!(fi%(prime[i]-1))){ll t1=fi/(prime[i]-1),t2=n,t3=1LL;while (!(t1%t3)){t2*=prime[i];solve(t1/t3,t2,i-1);t3*=prime[i];}//除去所有prime[i]的因子，枚举所有的n}if (fi==1LL){ans[++anslen]=n;return;}//这句话必须得放在最后，以防给出的fi=1，放在前面的话会漏掉2
}
int main(){srand(6662333);ll fi;int K;scanf("%lld%d",&fi,&K);Get_Prime();solve(fi,1LL,pcnt);
//must satisfy ans.size()>=Ksort(ans+1,ans+1+anslen);for (int i=1;i<K;i++) printf("%lld ",ans[i]);printf("%lld\n",ans[K]);
//注意这题不能有行末空格！return 0;
}这篇关于BZOJ 4803 逆欧拉函数 线性筛素数+dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
