题目大意：给一个正整数n，求出在[1, n]区间内和n互质的正整数的个数。Euler's Totient（欧拉函数）的直接应用。
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 #include <bitset> 5 using namespace std; 6 typedef vector<int> vi; 7 typedef long long ll; 8 #define MAXN 10000000 9 10 bitset<MAXN+100> bs; 11 vi primes; 12 13 void sieve(ll upper) 14 { 15 bs.set(); 16 bs.set(0, false); 17 bs.set(1, false); 18 for (ll i = 2; i <= upper; i++) 19 { 20 if (bs.test((size_t)i)) 21 for (ll j = i*i; j <= upper; j++) 22 bs.set((size_t)j, false); 23 primes.push_back((int)i); 24 } 25 } 26 27 vi primeFactors(ll n) 28 { 29 vi factors; 30 int idx = 0, pf = primes[idx]; 31 while (n != 1 && (pf*pf <= n)) 32 { 33 while (n % pf == 0) 34 { 35 n /= pf; 36 factors.push_back(pf); 37 } 38 pf = primes[++idx]; 39 } 40 if (n != 1) factors.push_back(n); 41 return factors; 42 } 43 44 int main() 45 { 46 #ifdef LOCAL 47 freopen("in", "r", stdin); 48 #endif 49 sieve(MAXN); 50 int n; 51 while (scanf("%d", &n) && n) 52 { 53 vi factors = primeFactors(n); 54 vi::iterator last = unique(factors.begin(), factors.end()); 55 int result = n; 56 for (vi::iterator it = factors.begin(); it != last; it++) 57 result = result - result/(*it); 58 printf("%d ", result); 59 } 60 return 0; 61 }