1、   欧拉函数

2、总结：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define max(a,b) a>b?a:b#define F(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=10010,MAX=1000100;int phi[MAX];void Init(){ F(i,1,MAX){ phi[i]=i; } F(i,2,MAX){ //注：从2开始 if(phi[i]==i){ for(int j=i;j<=MAX;j+=i){ phi[j]=phi[j]/i*(i-1); } } }}int main(){ Init(); int t,n; int a[N]; scanf("%d",&t); F(cas,1,t) { scanf("%d",&n); F(i,1,n){ scanf("%d",&a[i]); } LL sum=0; F(i,1,n){ F(j,a[i]+1,MAX){ if(phi[j]>=a[i]){ sum+=j; break; } } } printf("Case %d: %lld Xukha\n",cas,sum); } return 0;}