Description For given integer N N N (1 ≤ N ≤ 1 0 4 1\leq N\leq 10^4 1 ≤ N ≤ 1 0 4 ) find amount of positive numbers not greater than N N N that coprime with N N N . Let us call two positive integers (say, A A A and B B B , for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A A A and B B B are coprime iff g c d ( A , B ) = 1 \mathrm{gcd}\left(A,B\right) = 1 gcd ( A , B ) = 1 ).
Input file contains integer N N N .
Output Write answer in output file.
Sample Output Analysis 我首先想到的是欧拉函数 φ ( N ) \varphi\left(N\right) φ ( N ) ,后来发现数据量并不是特别的大,所以又用暴力做了一遍,也 AC 了。
这道题目的重点在于欧拉函数 φ ( N ) \varphi\left(N\right) φ ( N ) 的求法,现总结如下:
欧拉函数 φ ( N ) \varphi\left(N\right) φ ( N ) :小于等于 N N N 且与 N N N 互素的正整数的个数。
欧拉函数据有如下性质:
φ ( 1 ) = 1 \varphi\left(1\right) = 1 φ ( 1 ) = 1 φ ( N ) = N ⋅ ∑ p ∣ N ( p − 1 p ) \varphi\left(N\right) = N\cdot\sum_{p|N}{\left(\frac{p-1}{p}\right)} φ ( N ) = N ⋅ ∑ p ∣ N ( p p − 1 ) ,其中 p p p 为素数φ ( p k ) = p k − p k − 1 = ( p − 1 ) p k − 1 \varphi\left(p^k\right) = p^k - p^{k - 1} = \left(p-1\right)p^{k - 1} φ ( p k ) = p k − p k − 1 = ( p − 1 ) p k − 1 ,其中p为素数φ ( m n ) = φ ( m ) ⋅ φ ( n ) \varphi\left(mn\right)=\varphi\left(m\right)\cdot \varphi\left(n\right) φ ( mn ) = φ ( m ) ⋅ φ ( n ) ,其中 g c d ( m , n ) = 1 \mathrm{gcd}\left(m,n\right)=1 gcd ( m , n ) = 1 根据第 2 个式子我们就可以求出欧拉函数。
基本思路:首先置 φ ( N ) = N \varphi\left(N\right) = N φ ( N ) = N ,然后枚举 N N N 的素因子 p p p ,将 p p p 的整数倍的欧拉函数 φ ( k ⋅ p ) \varphi\left(k\cdot p\right) φ ( k ⋅ p ) 置 φ ( k ⋅ p ) = φ ( k ⋅ p ) ⋅ p − 1 p \varphi\left(k\cdot p\right) = \varphi\left(k\cdot p\right) \cdot \frac{p - 1}{p} φ ( k ⋅ p ) = φ ( k ⋅ p ) ⋅ p p − 1 即可。
基本代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std ;
const int MAX = 1024 ;
int N ;
int p [ MAX ], phi [ MAX ];
int main ()
{
cin >> N ;
for ( int i = 1 ; i <= N ; i ++ ) // 初始化
{ p [ i ] = 1 ; phi [ i ] = i ; }
p [ 1 ] = 0 ; // 1不是素数
for ( int i = 2 ; i <= N ; i ++ ) // 筛素数
{
if ( p [ i ])
{
for ( int j = i * i ; j <= N ; j += i )
{ p [ j ] = 0 ; }
}
}
for ( int i = 2 ; i <= N ; i ++ ) // 求欧拉函数
{
if ( p [ i ])
{
for ( int j = i ; j <= N ; j += i ) // 处理素因子p[i]
{
phi [ j ] = phi [ j ] / i * ( i - 1 ); // 先除后乘,防止中间过程超出范围
}
}
}
cout << "Primes: " << endl ;
for ( int i = 1 ; i <= N ; i ++ )
{ if ( p [ i ]) { cout << i << " " ; } }
cout << endl ;
cout << "Euler Phi Function: " << endl ;
for ( int i = 1 ; i <= N ; i ++ )
{ cout << phi [ i ] << " " ; }
return 0 ;
}
Copy Solution 欧拉函数 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std ;
int phi ( int x );
int main ()
{
int N ;
cin >> N ;
cout << phi ( N ) << endl ;
cout << endl ;
return 0 ;
}
int phi ( int x )
{
int nRet = x ;
int nTmp = ( int ) sqrt ( x );
for ( int i = 2 ; i <= nTmp ; i ++ )
{
if ( x % i == 0 )
{
nRet = nRet / i * ( i - 1 );
while ( x % i == 0 )
{ x /= i ; }
}
}
if ( x > 1 )
{
nRet = nRet / x * ( x - 1 );
}
return nRet ;
}
Copy 暴力 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std ;
int gcd ( int x , int y );
int main ()
{
int N , nRet = 0 ;
cin >> N ;
for ( int i = 1 ; i <= N ; i ++ )
{
if ( gcd ( N , i ) == 1 )
{ nRet ++ ; }
}
cout << nRet << endl ;
return 0 ;
}
int gcd ( int x , int y )
{
if ( y == 0 ) { return x ; }
return gcd ( y , x % y );
}
Copy SGU 不愧是经典题目的合集,每做一道题都会学到一些新的东西。