題意：題目給出一個(gè)歐拉函數(shù)值F（X），讓我們求>=這個(gè)函數(shù)值的最小數(shù)N，使得F（N） >= F(X);

　　分析：這個(gè)題目有兩種做法。第一種，暴力打出歐拉函數(shù)表，然后將它調(diào)整成有序的，再建立一個(gè)新的表格記錄滿足條件的最小的歐拉值。

　　第二種，根據(jù)歐拉函數(shù)的性質(zhì)，針對(duì)一個(gè)素?cái)?shù)N，F（N） = N-1; 然后假設(shè)第一個(gè)大于N的素?cái)?shù)為M，它的函數(shù)值為M-1，這時(shí)，在（N，M）之間的任何一個(gè)數(shù)都是合數(shù)，并且他們的歐拉值一定小于M-1，所以我們要找到題目中要求的最小數(shù)，可以從比它大一的數(shù)開始找，直到找到第一個(gè)素?cái)?shù)為止，這個(gè)數(shù)就是我們要找的最小值。

　　注意：C++編譯器不支持%I64，只支持%lld，我因?yàn)檫@個(gè)WA了幾次，要注意編譯器的要求和題目上方的說明。

　　代碼如下：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 1500100 #define LL long long LL prime[maxn+100]; void make() {memset(prime,1,sizeof(prime));prime[1] = 0;for(int i = 2; i <= maxn; i++){if(prime[i]){for(int j = i*2; j <= maxn; j += i){prime[j] = 0;}}} } int main() {LL t,n,num,ca = 0;make();LL sum;scanf("%lld",&t);while(t--){scanf("%lld",&n);sum = 0;for(int i = 0; i < n; i++){scanf("%lld",&num);for(LL j = num+1; true; j++){if(prime[j]){// printf("the min one = %d\n",j);sum += j;break;}}}printf("Case %lld: ",++ca);printf("%lld Xukha\n",sum);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/jifahu/p/5583666.html

總結(jié)

以上是生活随笔為你收集整理的LightOJ 1370 Bi-shoe and Phi-shoe（欧拉函数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。