求1-n中与n互素的个数

一、第一种求法

　　思路：枚举1-n之间的数，判断n，i的最大公约数是否为1，为1则与n互素

　　代码实现：

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include <string>
 6 #include 
 7 #include 
 8 #include 
 9 #include <set>
10 #include 
11 #include 
12 #include 
13 #define PII pair
14 #define rep(i,z,n) for(int i = z;i <= n; i++)
15 #define per(i,n,z) for(int i = n;i >= z; i--)
16 #define ll long long
17 #define db double
18 #define vi vector
19 #define debug(x) cerr << "!!!" << x << endl;
20 using namespace std;
21 inline ll read()
22 {
23     ll s,r;
24     r = 1;
25     s = 0;
26     char ch = getchar();
27     while(ch < '0' || ch > '9'){
28         if(ch == '-')
29             r = -1;
30         ch = getchar();
31     }
32     while(ch >= '0' && ch <= '9'){
33         s = (s << 1) + (s << 3) + (ch ^ 48);
34         ch = getchar();
35     }
36     return s * r;
37 }
38 inline void write(ll x)
39 {
40     if(x < 0) putchar('-'),x = -x;
41     if(x > 9) write(x / 10);
42     putchar(x % 10 + '0');
43 }
44 ll gcd(int a,int b)
45 {
46     if(!b) return a;
47     return gcd(b,a % b);
48 }
49 void solve(ll n)
50 {
51     int cnt = 0;
52     for(int i = 1;i < n;i++)
53         if(gcd(n,i) == 1){
54             cout << i << endl;
55             cnt++;
56         }
57     cout << cnt << endl;
58 }
59 int main()
60 {
61     ll n;
62     n = read();
63     solve(n);
64     return 0;
65 }

二、第二种求法

　　采用欧拉函数求解，由欧拉函数的性质可得1-n中与n互素的个数为n*(1-1/pi)*(1-p(i+1))...... (pi为n的素因子)

　　有了这个公式，我们便只需要判断这个数是否是素数，是否为n的因子，然后进行相乘操作即可。

　　代码实现：

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include <string>
 6 #include 
 7 #include 
 8 #include 
 9 #include <set>
10 #include 
11 #include 
12 #include 
13 #define PII pair
14 #define rep(i,z,n) for(int i = z;i <= n; i++)
15 #define per(i,n,z) for(int i = n;i >= z; i--)
16 #define ll long long
17 #define db double
18 #define vi vector
19 #define debug(x) cerr << "!!!" << x << endl;
20 using namespace std;
21 inline ll read()
22 {
23     ll s,r;
24     r = 1;
25     s = 0;
26     char ch = getchar();
27     while(ch < '0' || ch > '9'){
28         if(ch == '-')
29             r = -1;
30         ch = getchar();
31     }
32     while(ch >= '0' && ch <= '9'){
33         s = (s << 1) + (s << 3) + (ch ^ 48);
34         ch = getchar();
35     }
36     return s * r;
37 }
38 inline void write(ll x)
39 {
40     if(x < 0) putchar('-'),x = -x;
41     if(x > 9) write(x / 10);
42     putchar(x % 10 + '0');
43 }
44 bool isprime(int k)
45 {
46     for(int i = 2;i <= sqrt(k);i++)
47         if(k % i == 0)
48             return false;
49     return true;
50 }
51 void solve(ll n)
52 {
53     double cnt = n;
54     for(int i = 2;i <= sqrt(n);i++)
55         if(isprime(i) && n % i == 0){
56             cnt = cnt * (1 - 1.0 / i);
57             cout << cnt << endl;
58         }
59     cout << cnt << endl;
60 }
61 int main()
62 {
63     ll n;
64     n = read();
65     solve(n);
66     return 0;
67 }

收获还是挺多的，学了个欧拉函数公式

离散数学

相关

关于离散数学到了期末这件事

标签