uva 10280（欧拉函数）

题意：找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 <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
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<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> 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<LEN; i++)
56         dp[i] = dp[i-1] + Euler(i);
57     while(cin >> n){
58         if(!n) break;
59         cout << (dp[n]-1) * 2 + 1 << endl;
60     }
61     return 0;
62 }

View Code