題目鏈接：http://lightoj.com/volume_showproblem.php?problem=1370

?

題意：給你n個數(shù)，每個數(shù)要找一個歐拉函數(shù)值大于等于這個數(shù)，并求和。

?

題解：就是素數(shù)打個表，歐拉函數(shù)值是 < n的最大互質(zhì)個數(shù)，但這題可以等于，素數(shù)x的歐拉函數(shù)值是 x - 1，所以從x + 1 開始判斷。這題是利用了歐拉函數(shù)的思想。

?

1 #include<iostream> 2 using namespace std; 3 #define ll long long 4 const int N = 1e6 + 10; 5 bool prime[N]; 6 7 void init(){ 8 for(int i = 0; i < N ;i++){ 9 prime[i] = true; 10 } 11 prime[1] = false; 12 for(int i = 2; i < N; i++){ 13 for(int j = i + i; j <= N; j += i){ 14 prime[j] = false; 15 } 16 } 17 18 } 19 20 int main(){ 21 init(); 22 /* 23 for(int i = 0 ; i < 10 ; i++){ 24 cout<<prime[i]<<endl; 25 } */ 26 int T,n; 27 cin>>T; 28 29 for(int t = 1; t <= T ; t++){ 30 cin>>n; 31 ll ans = 0; 32 int x; 33 for(int i = 0 ; i < n; i++){ 34 cin>>x; 35 for(int j = x+1 ;;j++){ 36 if(prime[j]){ 37 // cout<<j<<endl; 38 ans += j; 39 break; 40 } 41 } 42 } 43 44 cout<<"Case "<<t<<": "<<ans<<" Xukha"<<endl; 45 } 46 return 0; 47 } View Code

?

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

總結(jié)

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

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