本文共 1230 字，大约阅读时间需要 4 分钟。
这题看着很唬人，但实际上是道水题...
f[n]通过打表或证明，可以发现就是欧拉函数，g[n]恒等于n，所以题目的意思就是让你求n的k次欧拉函数。
可以发现实际上k次欧拉函数，n的数值减小得很快，所以直接暴力即可。
code：真的暴力
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define LL long long#define FILE "dealing"#define up(i,j,n) for(LL i=j;i<=n;i++)LL read(){ LL x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); return x*f;}const LL maxn=1600000,mod=1000000007,inf=1000000000;bool cmin(LL& a,LL b){return a>b?a=b,true:false;}bool cmax(LL& a,LL b){return a >=1)if(b&1)ans*=a;return ans;}LL qiuoula(LL n){ LL m=(LL)sqrt(n*1.0+1),sum=1; cnt=0; up(i,2,m){ if(n==1)break; while(n%i==0){ n/=i; if(c[cnt]==i)r[cnt]++; else c[++cnt]=i,r[cnt]=1; } if(c[cnt]==i) sum*=(mul(c[cnt],r[cnt])-mul(c[cnt],r[cnt]-1)); } if(n>1)sum*=(n-1); return sum; }int main(){ //freopen(FILE".in","r",stdin); //freopen(FILE".out","w",stdout); LL n=read(),m=(read()+1)/2; up(i,1,m){ n=qiuoula(n); if(n==1)break; } cout< <
转载于:https://www.cnblogs.com/chadinblog/p/6437646.html