数学知识

算数基本定理

任何大于 1 的整数是质数或独一无二的质数乘积（不理次序）。

任何一个大于1的自然数n都可以表示为素数的乘积形式：

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve(int n) {
  vector<int> vec;
  for (int i = 1; i <= n / i; i++) {
    if (n % i == 0)
      {
        vec.push_back(i);
        if (i != n / i)
            vec.push_back(n / i);
      }
    
  }
  sort(vec.begin(),vec.end());
    for(auto i : vec)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
  int n;
  cin >> n;
  while(n --)
  {
    int x;
    cin >> x;
    solve(x);
  }
 
}

870. 约数个数

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
#include <iostream>
#include <unordered_map>

using namespace std;

long long mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  unordered_map<int, int> cnt;
  while (n--) {
    int x;
    cin >> x;
    for (int i = 2; i <= x / i; i++) {
      while (x % i == 0) {
        x /= i;
        cnt[i]++;
      }
    }
    if (x > 1)      //n也是一个质因子
      cnt[x]++;
  }
  long long ans = 1;
  for (auto c : cnt) {
       //res = (x1+1)(x2+1)(x3+1)…(xk+1)
    ans = ans * (c.second + 1) % mod;
  }
  cout << ans << endl;
}

871. 约数求和

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
#include <iostream>
#include <unordered_map>

using namespace std;
#define LL long long
long long mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  unordered_map<int, int> cnt;
  while (n--) {
    int x;
    cin >> x;
    for (int i = 2; i <= x / i; i++) {
      while (x % i == 0) {
        x /= i;
        cnt[i]++;
      }
    }
    if (x > 1)      //n也是一个质因子
      cnt[x]++;
  }
  long long res = 1;

    for (auto p : cnt)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        //t = 1   t = p + 1   t = p^2 + p + 1
        res = res * t % mod;
    }

    cout << res << endl;



  cout << ans << endl;
}

872. 最大公约数

欧几里得算法（辗转相除法）：

(a， b) = (a % b， b) = （b, a %b）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;


int gcd(int a, int b)
{
    return b == 0? a : gcd(b, a % b);
}


int main()
{
    int n, a, b;
    cin >> n;
    while(n--)
    {
        cin >> a >> b;
        cout << gcd(a,b) << endl;
    }
}

欧拉函数

873. 欧拉函数

如果 (n) 的质因数分解为：

那么，欧拉函数可以表示为：

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
43
#include <iostream>

using namespace std;
const int  N = 100010;

typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    int res = n;
    for(int i = 2; i <= n / i; i++)
    {
        if(n % i == 0)
        {
            
            // res*=(p - 1) / p
            res = res / i * (i - 1);
            while(n % i == 0)   //对n约分
            {
                n /= i;
            }
        }
    }
    // 如果有剩余，则剩余是个质因子
    if(n > 1)
    {
        res = res / n * (n - 1);
    }
    cout <<res << endl;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        solve();
    }
}


874. 筛法求欧拉函数

AcWing 874. 筛法求欧拉函数 - AcWing

AcWing 874. 筛法求欧拉函数 - AcWing

phi[primes[j] i]分为两种情况：
① i % primes[j] == 0时：primes[j]是i的最小质因子，也是primes[j] i的最小质因子，因此1 - 1 / primes[j]这一项在phi[i]中计算过了，只需将基数N
𝑁
修正为primes[j]倍，最终结果为phi[i] primes[j]。
② i % primes[j] != 0：primes[j]不是i的质因子，只是primes[j] i的最小质因子，因此不仅需要将基数N
𝑁
修正为primes[j]倍，还需要补上1 - 1 / primes[j]这一项，因此最终结果phi[i] * (primes[j] - 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 1000010;

int primes[N], cnt;
int phi[N];
bool st[N];

void get_eulers(int n) {
  phi[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!st[i]) {
      primes[cnt++] = i;
      phi[i] = i - 1; // 若为质数，有i - 1个数与其互质
    }
    for (int j = 0; primes[j] <= n / i; j++) {
      st[primes[j] * i] = true;
      if (i % primes[j] == 0) //最小质因子
      {
        phi[primes[j] * i] = phi[i] * primes[j];
        /*
  当p[j]是i的一个约数时,i的质因数与p[j]*i的质因数完全相同。
  i      = (p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^ap[j])...(pk^ak)
  i*p[j] = (p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^(ap[j]+1))...(pk^ak)
  由欧拉函数的定义可知：
  Φ(i)      =  i   * (1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
  Φ(i*p[j]) = i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
  */
        break;
      }
      /*
当i%p[j]!=0时，p[j]不是i的约数，i与i*p[j]的质因子相差一个p[j]
i      = (p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)
i*p[j] = (p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)*(p[j]^ap[j])
所以由欧拉函数的定义可知：
Φ(i)      =  i    *(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)
Φ(i*p[j]) = i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)(1-1/p[j])
*/
      phi[primes[j] * i] = phi[i] * (primes[j] - 1);
    }
  }
}

int main() {
  int n;
  cin >> n;

  get_eulers(n);

  LL res = 0;
  for (int i = 1; i <= n; i++)
    res += phi[i];
  printf("%lld\n", res);

  return 0;
}

欧拉定理

欧拉定理是数论中的一个重要定理，它描述了在模 (m) 的整数环中，与 (m) 互质的整数 (a) 和 (m) 的欧拉函数 (\varphi(m)) 之间的关系。以下是欧拉定理的表述：
如果 (m) 是一个正整数，(a) 是一个与 (m) 互质的正整数，那么 (a^{\varphi(m)} \equiv 1 \pmod{m})。
其中，(\varphi(m)) 表示小于或等于 (m) 的与 (m) 互质的正整数的个数，这个函数被称为欧拉函数。
以下是欧拉定理的Markdown格式表示：

1
2
3
4
5
# 欧拉定理
欧拉定理是数论中的一个基本定理，其内容如下：
如果 \( m \) 是一个正整数，\( a \) 是一个与 \( m \) 互质的正整数，那么：
\[ a^{\varphi(m)} \equiv 1 \pmod{m} \]
这里，\(\varphi(m)\) 是欧拉函数，表示小于或等于 \( m \) 的与 \( m \) 互质的正整数的个数。

当你将上述Markdown文本放入支持Markdown的编辑器中时，它将被渲染为格式化的文本，如下所示：

欧拉定理和费马丁柳

欧拉定理：
如果 ( m ) 是一个正整数，( a ) 是一个与 ( m ) 互质的正整数

那么：

费马小定理:
如果 ( p ) 是一个素数（有p-1个数与其互质），而 ( a ) 是一个不被 ( p ) 整除的整数，那么：

快速幂

875. 快速幂

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
#include <iostream>

using namespace std;

typedef long long LL;                            



int qmi(int a, int k, int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;		//注意转型，因为我们传入的类型为int
        k = k >> 1;
        //更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
        a = (LL)a * a % p;
    }
    return res;
}



int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, k , p;
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }    
}

876. 快速幂求逆元

费马定理+快速幂 [AcWing 876. 快速幂求逆元 - AcWing](https://www.acwing.com/solution/content/3054/) a / b ≡ a * x (mod n) 两边同乘b可得 a ≡ a * b * x (mod n) 即 1 ≡ b * x (mod n) 同 b * x ≡ 1 (mod n) 由费马小定理可知，当n为质数时 b ^ (n - 1) ≡ 1 (mod n) 拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n) 故当n为质数时，b的乘法逆元 x = b ^ (n - 2) 
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
#include <iostream>

using namespace std;

typedef long long LL;                            

//a^k%p
int qmi(int a, int k, int p)
{
    LL res  = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, p;
        cin >> a >> p;
        int res = qmi(a, p - 2, p);
        if(a % p)  cout << res << endl;	//互质存在逆元
        else cout <<"impossible"<< endl;
    }
}

拓展欧几里得算法