例题

欧拉函数/素数判定

题目链接

题目

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;

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

欧拉筛

#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;

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

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;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
 

• 如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai
  

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/90488830