uva 10280（欧拉函数）-白红宇

uva 10280（欧拉函数）

阅读量：6953 次

发布时间：2019-06-27

本文共 1384 字，大约阅读时间需要 4 分钟。

题意：找n以内有多少对互质的数。

思路：欧拉函数预处理一下，然后答案等于（∑Euler(i)-1）*2 + 1 i从1到n。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-03-28 18:19 5  * Filename     : uva_10820.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 500010;34 int dp[LEN];35 36 int Euler(int n)37 {38 int ans = n;39 for(int i=2; i<=sqrt(n); i++){40 if(n%i == 0){41 ans = ans / i * (i-1);42 while(n%i == 0) n /= i;43 }44 } 45 if(n > 1) ans = ans / n * (n-1);46 return ans;47 }48 49 int main()50 {51 // freopen("in.txt", "r", stdin);52 53 int n;54 dp[0] = 0;55 for(int i=1; i
                      
                       > n){58 if(!n) break;59 cout << (dp[n]-1) * 2 + 1 << endl;60 }61 return 0;62 }