歐拉函數/歐拉函數打表 lightoj1370(java/c++ )

例題

歐拉函數/素數判定

​​題目連結​​

題目

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

}      

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​

  ​