题目大意 给n，求欧拉函数Φ(x)>=n的最小的那个x。 解题思路 根据欧拉函数，素数n的欧拉函数值一定是n-1；然后让求最小的x,还要大于等于n，所以从n+1开始找素数就可以了 我自己居然考虑了会要不要减一，然后意识到求的x值而不是x的欧拉函数值
关于欧拉函数（摘自百度 在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
代码如下
#include<iostream> using namespace std; const int maxn=1e6+10; int a[maxn]; void prime() { int i,j; a[0]=1; a[1]=1; for(i=2;i<maxn;i++) { if(a[i]==0) { for(j=i+i;j<=maxn;j+=i) { a[j]=1; } } } } int main() { prime(); int t,n,i,k,x=0; cin>>t; while(t--) { long long ans=0; //卡了一次 cin>>n; while(n--) { cin>>k; for(i=k+1;;i++) { if(a[i]==0) { ans+=i; break; } } } x++; cout<<"Case "<<x<<": "; cout<<ans<<" Xukha"<<endl; } return 0; }