例題
歐拉函數/素數判定
題目
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
#include
using namespace std;
#define ll long long
bool isprime(int index)
{
if(index<=2)return true;
else { for(int i=2;i*i
}
}
int main()
{ int t;cin>>t; for(int i=0;i>n;ll count=0; for(int j=0;j>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
#include
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>n;count=0; for(int j=0;j>team; int index=team+1; while(a[index]
}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
}
private static boolean isprime(int index) {
if(index<=2)return true;
else { for(int i=2;i*i
} }
private static int oula(int team) {
int i=0;int res=team;int team1=team;
for(i=2;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