例題

歐拉函數/素數判定

題目鏈接

題目

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

• 如果對后端、爬蟲、數據結構算法等感性趣歡迎關注我的個人公眾號交流：bigsai
  

總結

以上是生活随笔為你收集整理的欧拉函数/欧拉函数打表 lightoj1370(java/c++ )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。