欧拉函数

裸题。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 2010
15 
16 int fat[mnx];
17 int main(){
18     LL n;
19     while( scanf( "%I64d", &n ) != EOF && n ){
20         int cnt = 0;
21         double m = n;
22         for( LL i = 2; i * i <= n; ++i ){
23             if( n % i == 0 ){
24                 fat[cnt++] = i;
25                 while( n % i == 0 )
26                     n /= i;
27             }
28             if( n == 1 ) break;
29         }
30         if( n != 1 ) fat[cnt++] = n;
31         for( int i = 0; i < cnt; ++i )
32             m *= ( 1.0 - ( 1.0 / fat[i] ) );
33         printf( "%I64d
", (LL)(m+eps) );
34     }
35     return 0;
36 }

View Code

POJ 1284 Primitive Roots

题意：

就是给出一个奇素数，求出他的原根的个数。

定义：n的原根x满足条件0<x<n,并且有集合{ (xi mod n) | 1 <= i <=n-1 } 和集合{ 1, ..., n-1 }相等

定理：如果p有原根，则它恰有φ(φ(p))个不同的原根，p为素数，当然φ(p)=p-1,因此就有φ(p-1)个原根。。

具体看这里

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 2010
15 
16 int fat[mnx];
17 int main(){
18     LL n;
19     while( scanf( "%I64d", &n ) != EOF && n ){
20         int cnt = 0;
21         n--;
22         double m = n;
23         for( LL i = 2; i * i <= n; ++i ){
24             if( n % i == 0 ){
25                 fat[cnt++] = i;
26                 while( n % i == 0 )
27                     n /= i;
28             }
29             if( n == 1 ) break;
30         }
31         if( n != 1 ) fat[cnt++] = n;
32         for( int i = 0; i < cnt; ++i )
33             m *= ( 1.0 - ( 1.0 / fat[i] ) );
34         printf( "%I64d
", (LL)(m+eps) );
35     }
36     return 0;
37 }

View Code

POJ 2478 Farey Sequence

欧拉函数求和。用了一个线性求欧拉函数的模板。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 1000100
15 
16 int pri[mnx], tot;
17 LL phi[mnx];
18 bool isnot[mnx];
19 void init(){
20     phi[1] = 1;
21     for( int i = 2; i < mnx; ++i ){
22         if( !isnot[i] ){
23             phi[i] = i - 1;
24             pri[tot++] = i;
25         }
26         for( int j = 0; j < tot && i * pri[j] < mnx; ++j ){
27             isnot[i*pri[j]] = 1;
28             if( i % pri[j] == 0 ){
29                 phi[i*pri[j]] = phi[i] * pri[j];
30                 break;
31             }
32             else phi[i*pri[j]] = phi[i] * ( pri[j] - 1 );
33         }
34     }
35 }
36 int main(){
37     init();
38     for( int i = 3; i < mnx; ++i ){
39         phi[i] += phi[i-1];
40     }
41     int n;
42     while( scanf( "%d", &n ) != EOF && n ){
43         printf( "%I64d
", phi[n] );
44     }
45     return 0;
46 }

View Code

POJ 3090 Visible Lattice Points

从( 0, 0 )看，问右上角在( n, n )的正方形内，能够看到多少个点。就是( x, y )， x与y互质的点都能看到。就是欧拉函数求和 sum， sum*2 + 3就是答案了( 0, 0 ), ( 1, 0 ), ( 0, 1 )三个点也要算上。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 2010
15 
16 LL euler( LL x ){
17     double ret = x;
18     for( LL i = 2; i * i <= x; ++i ){
19         if( x % i == 0 )
20             ret *= ( i - 1.0 ) / i;
21         while( x % i == 0 )
22             x /= i;
23     }
24     if( x > 1 ) ret *= ( x - 1.0 ) / x;
25     return (LL)( ret + eps );
26 }
27 int main(){
28     LL n;
29     int cas, kk = 1;
30     scanf( "%d", &cas );
31     while( cas-- ){
32         scanf( "%I64d", &n );
33         printf( "%d %I64d ", kk++, n );
34         LL ans = 0;
35         for( int i = 2; i <= n; ++i )
36             ans += euler( (LL)i );
37         printf( "%I64d
", ans * 2 + 3 );
38     }
39     return 0;
40 }

View Code

POJ 3696 The Luckiest number

题意：给你一个数L,让你求出最小的一个数能被L整除，这个数满足每一位都是8，问这个数最少有多少位。

首先设这个有k位，则这个数可以表示为 8 / 9 * ( 10^k - 1 ) = L * m

-> 8 * ( 10^k - 1 ) = 9 * L * m;

设 d = gcd( 9L, 8 ) -> 8 / gcd( 9L, 8 ) * ( 10^k - 1 ) = 9 * L / gcd( 9L, 8 ) * m;

因为 8/gcd(9L,8) 与 9L/gcd(9L,8) 互质，则等式成立的话， (10^k-1) % ( 9L/gcd(9L,8) ) == 0;

gcd(9L, 8) = gcd(L, 8)。即 ( 10^k ) % ( 9L/gcd(L,8) ) == 1。。设 q = 9L/gcd(L,8)。。

由欧拉定理，当gcd(10,q) == 1，k = phi(q)是其中一个解。要求最小解，就要枚举phi(q)的所有因子，看是否满足 10^k % ( phi(q)的因子 ) == 1，取最小的那个。

若gcd( 10, q ) != 1，很明显方程无解。用了快速幂和二进制乘法( 因为有可能爆longlong)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 100100
15 
16 LL gcd( LL a, LL b ){
17     return b == 0 ? a : gcd( b, a % b );
18 }
19 LL phi( LL x ){
20     double ret = x;
21     for( LL i = 2; i * i <= x; ++i ){
22         if( x % i == 0 )
23             ret *= ( i - 1.0 ) / i;
24         while( x % i == 0 )
25             x /= i;
26     }
27     if( x > 1 ) ret *= ( x - 1.0 ) / x;
28     return (LL)( ret + eps );
29 }
30 LL m, L;
31 LL mul( LL a, LL b ){
32     LL ret = 0;
33     while( b ){
34         if( b & 1 ) ret = ( ret + a ) % m;
35         a = ( a + a ) % m;
36         b >>= 1;
37     }
38     return ret;
39 }
40 int qpow( LL k ){
41     LL ret = 1, x = 10;
42     while( k ){
43         if( k & 1 ) ret = mul( ret, x ) % m;
44         x = mul( x, x ) % m;
45         k >>= 1;
46     }
47     return ret == 1 ? 1 : 0;
48 }
49 int main(){
50     int kk = 1;
51     while( scanf( "%I64d", &L ) != EOF && L ){
52         m = 9 * L / gcd( L, 8 );
53         LL sum = phi( m ), ans = 1e15;
54         //cout << sum << endl;
55         if( gcd( 10, m ) != 1 ){
56             printf( "Case %d: 0
", kk++ ); continue;
57         }
58         for( LL i = 1; i * i <= sum; ++i ){
59             if( sum % i == 0 ){
60                 if( qpow( i ) )
61                     ans = min( ans, i );
62                 if( qpow( sum / i) )
63                     ans = min( ans, sum/i );
64             }
65         }
66         printf( "Case %d: %I64d
", kk++, ans );
67     }
68     return 0;
69 }

View Code

POJ 3358 Period of an Infinite Binary Expansion

输入一个<1的分数，问你将这个小于1的小数转化为二进制形式，求最小循环部分的起始位置以及最小的循环长度。

观察 1/10 这组。按照二进制转换法，得到 1/10, 2/10, 4/10, 8/10, 16/10, 32/10。。

对每个分子 %10, 就可以得到 1/10, 2/10, 4/10, 8/10, 6/10, 2/10。。出现了重复，这个重复就是最小的循环长度。

对于输入的分子pp，分母qq，首先 p = pp / gcd( pp, qq ), q = qq / gcd( pp, qq )。则 p * 2^i = p * 2^j mod q 就得到

p * 2^i * ( 2^(j-i) - 1 ) = 0 ( mod q ); 因为gcd( p, q ) == 1，所以 q | 2^i * ( 2^(j-i) - 1 );

因为 2^(j-i) - 1是奇数，所以 q 里面有多少个 2的幂，i 就是多少。i就是循环开始位置的前一个位置。令q'为q除去2的幂之后的数，则

q' | 2^(j-i) - 1。。也就是求出 2^x == 1 ( mod q' ); 因为gcd( 2, q' ) == 1，所以phi( q' ) 是其中一个解。就像上一题一样找最小解就好了。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 #include<queue>
 8 
 9 using namespace std;
10 
11 #define inf 1e16
12 #define eps 1e-6
13 #define LL long long
14 #define ULL unsigned long long
15 #define MP make_pair
16 #define pb push_back
17 #define mnx 1220
18 
19 LL gcd( LL a, LL b ){
20     return b == 0 ? a : gcd( b, a % b );
21 }
22 LL phi( LL x ){
23     double ret = x;
24     for( LL i = 2; i * i <= x; ++i ){
25         if( x % i == 0 )
26             ret *= ( i - 1.0 ) / i;
27         while( x % i == 0 )
28             x /= i;
29     }
30     if( x > 1 ) ret *= ( x - 1.0 ) / x;
31     return (LL)( ret + eps );
32 }
33 LL a, b;
34 LL mul( LL x, LL y ){
35     LL ret = 0;
36     while( y ){
37         if( y & 1 ) ret = ( ret + x ) % b;
38         x = ( x + x ) % b;
39         y >>= 1;
40     }
41     return ret;
42 }
43 int qpow( LL k ){
44     LL ret = 1, x = 2;
45     while( k ){
46         if( k & 1 ) ret = mul( ret, x );
47         x = mul( x, x );
48         k >>= 1;
49     }
50     return ret == 1 ? 1 : 0;
51 }
52 int main(){
53     int kk = 1;
54     while( scanf( "%I64d/%I64d", &a, &b ) != EOF ){
55         if( a == 0 ){
56             printf( "Case #%d: 1,1
", kk++ ); continue ;
57         }
58         LL d = gcd( a, b );
59         a /= d, b /= d;
60         LL ans1 = 1, ans2 = inf;
61         while( b % 2 == 0 ){
62             b /= 2;
63             ans1++;
64         }
65         LL s = phi( b );
66         for( LL i = 1; i * i <= s; ++i ){
67             if( s % i == 0 ){
68                 if( qpow( i ) )
69                     ans2 = min( ans2, i );
70                 if( qpow( s/i ) )
71                     ans2 = min( ans2, s/i );
72             }
73         }
74         printf( "Case #%d: %I64d,%I64d
", kk++, ans1, ans2 );
75     }
76     return 0;
77 }

View Code