题目
Bamboo Pole-vault是Xzhiland的一项大受欢迎的运动。 Phi-shoe大师是他成功的非常受欢迎的教练。他需要为他的学生提供一些竹子，所以他让他的助手Bi-Shoe去市场购买。市场上有很多可能的整数长度的Bamboos（是的！）。根据Xzhila的传统，
竹子的分数=Φ（竹子的长度）
（Xzhilans非常喜欢数论）。对于您的信息，Φ（n）=小于n的数字，它们相对于素数（除了1之外没有公约数）到n。因此，长度为9的竹子的得分为6，因为1,2,4,5,7,8是9的相对素数。
助理双鞋必须为每个学生买一个竹子。作为一个扭曲，Phi-shoe的每个撑杆跳学生都有一个幸运数字。 Bi-shoe希望购买竹子，这样他们每个人都会得到一张分数大于或等于他/她的幸运数字的竹子。 Bi-shoe希望最大限度地减少购买竹子所花费的总金额。一个竹子单位花费1 Xukha。帮助他
输入
输入以整数T（≤100）开始，表示测试用例的数量。
每个案例都以包含整数n（1≤n≤10000）的行开头，表示Phi-shoe的学生人数。下一行包含n个空格分隔的整数，表示学生的幸运数字。每个幸运数字将位于[1,106]范围内。
输出
对于每种情况，打印案例编号和购买竹子所花费的最少金额。有关详细信息，请参阅示例
Sample Input
3
5
1 2 3 4 5
6
10 11 12 13 14 15
2
1 1
Sample Output
Case 1: 22 Xukha
Case 2: 88 Xukha
Case 3: 4 Xukha
题意
题意：给你n个整数，第i个整数为Xi。定义phi(k)为k的欧拉函数值，设pi为满足phi(pi)>=Xi的最小整数，题目就是要求sum(p1,p2,p3,…,pn)。
告诉你幸运数字x，你找出phi(n)=x的这个最小的n，若干个这样数的合。
首先要清楚几个概念phi(n)=n-1，n为素数时候。因为n和小于它的任意都互质。
所以解题思路大致有两个：
欧拉函数的角度：
欧拉是最明显的，要找出大于这个数最小的那个phi[i],如果单个欧拉函数求会TL所以需要欧拉打表。没输入一个数网上找几个就行了
素数角度
n为素数时候，phi(n)=n-1，所以第一个phi(i)=t的那个i就是在t右侧的第一个素数。有了这个思路你就可以用素数解决问题，可以用素数筛。用直接的素数判定也能过。
c++代码：
直接判定
#include <iostream> #include<stdio.h> using namespace std; #define ll long long bool isprime(int index) { if(index<=2)return true; else { for(int i=2;i*i<index+1;i++) { if(index%i==0)return false; } return true; } } int main() { int t;cin>>t; for(int i=0;i<t;i++) { int n;cin>>n;ll count=0; for(int j=0;j<n;j++) { ll team; cin>>team; int index=team+1; while(!isprime(index)) {index++;} count+=index; } //string s=" Xukha"; printf("Case %d: %lld Xukha\n",(i+1),count); } return 0; }
欧拉筛
#include <iostream> #include<stdio.h> using namespace std; #define ll long long const int MAXN=1100000+7; int m; ll a[MAXN],euler[MAXN]; void phi() { for(int i=1;i<=m;i++) a[i]=i; for(int i=2;i<=m;i+=2) a[i]>>=1; for(int i=3;i<=m;i++) { if(a[i]==i) { for(int j=i;j<=m;j+=i) a[j]=(a[j]/i)*(i-1); } } } int main() { m=1100000; phi(); int t;cin>>t; for(int i=0;i<t;i++) { ll n,count; cin>>n;count=0; for(int j=0;j<n;j++) { ll team; cin>>team; int index=team+1; while(a[index]<team) {index++;} count+=index; } printf("Case %d: %lld Xukha\n",(i+1),count); } return 0; }
java 欧拉打表（可以自己改成素数）
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Scanner; public class Main{ public static void main(String[] args) throws IOException { // TODO 自动生成的方法存根 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); in.nextToken();int t=(int)in.nval; int a[]=new int[1100001]; for(int i=1;i<1100001;i++) { a[i]=i; } for(int i=2;i+2<1100001;i+=2) { a[i]/=2; } for(int i=3;i+2<1100001;i+=2) { if(a[i]==i) { for(int j=i;j+i<=1100001;j+=i) { a[j]=a[j]/i*(i-1); } } } for(int i=0;i<t;i++) { in.nextToken();int n=(int)in.nval;long count=0; for(int j=0;j<n;j++) { in.nextToken(); long team=(long)in.nval; int index=(int) (team+1); while(a[index]<team) {index++;} count+=index; //System.out.println(oula(team)); } System.out.println("Case "+(i+1)+": "+count+" Xukha"); } } private static boolean isprime(int index) { if(index<=2)return true; else { for(int i=2;i*i<index+1;i++) { if(index%i==0)return false; } return true; } } private static int oula(int team) { int i=0;int res=team;int team1=team; for(i=2;i<(int)Math.sqrt(team1)+1;i++) { if(team%i==0) { res=res/i*(i-1); while(team%i==0) {team/=i;}//保证I是素数 } } if(team>1)res=res/team*(team-1); return res; } }
