/*
给定n个数ai，要求欧拉函数值大于ai的最小的数bi
求sum{bi}
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
int n,a[maxn];
int phi[maxn],m,v[maxn],prime[maxn];
void init(
int n){
memset(v,0,
sizeof v);
m=
0;
for(
int i=
2;i<n;i++
){
if(v[i]==
0){
//i是质数
v[i]=i,prime[++m]=
i;
phi[i]=i-
1;
}
for(
int j=
1;j<=m;j++
){
if(prime[j]>v[i] || prime[j]*i>n)
break;
v[i*prime[j]]=prime[j];
//筛素数
phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-
1:
prime[j]);
}
}
}
/*int phi[maxn];
void init(int n){//用era筛的思路O(nlogn)复杂度
phi[1]=1;
for(int i=2;i<=n;i++)phi[i]=i;
for(int i=2;i<=n;i++)
if(phi[i]==i)//i是质数
for(int j=1;i*j<=n;j++)
phi[i*j]=phi[i*j]/i*(i-1);
}*/
int main(){
int t,tt;
init(maxn);
cin>>
t;
for(tt=
1;tt<=t;tt++
){
cin>>
n;
for(
int i=
1;i<=n;i++)cin>>
a[i];
sort(a+
1,a+
1+
n);
int j=
1;
long long ans=
0;
for(
int i=
2;i<maxn;i++
){
while(phi[i]>=a[j] && j<=
n)
ans+=i,j++
;
}
printf("Case %d: %lld Xukha\n",tt,ans);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10380640.html
