Bi-shoe and Phi-shoe

题意：
给你一些数，对于每一个求出数且的欧拉函数的值不小于，并且是所有的N的和加起来最小。

欧拉函数板子题。

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int prime[maxn],vis[maxn],phi[maxn];
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
void initial(const int n=1e6+5) {
    int cnt=0; phi[1]=1;
    for(int i=2;i<=n;i++) {
        if(vis[i]==0) { prime[++cnt]=i; phi[i]=i-1;vis[i]=i; }
        for(int j=1;j<=cnt;j++) {
            if(prime[j]>vis[i]||i*prime[j]>n) break;
            vis[i*prime[j]]=prime[j];
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int a[maxn];
int main() {
    initial();
    int t=read(),cas=0;
    while(t--) {
        int n=read();
        ll ans=0;
        for(int i=1;i<=n;++i) a[i]=read();
        sort(a+1,a+1+n);
        for(int i=1,j=2;i<=n;++i) {
            while(phi[j]<a[i]) ++j;
            ans+=j;
        }
        printf("Case %d: %lld Xukha\n", ++cas, ans);
    }
    return 0;
}