知乎|数论——质数：分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//O(n)暴力
private static void divide(int n)
{

    for(int i = 2; i <= n; i++)//遍历从 2 到 n 的所有数
    {
        if(n % i == 0)//如果 i 是 n 的因数
        {
            int k = 0;
            while(n % i == 0)//除尽 (使i只会是x的质因数)
            {
                n /= i;
                k++;
            }
        }
    }
}

n的因数的质因数，肯定也是n的质因数
n的任何一个因数x,假如x是合数，那么x可以由n的小于x的质因数所相乘而得
一个数的因数，从小到大排序，最开始的因数肯定是质因数，后面才有合数
x是n的因数，且x是合数，那么n的质因数不一定是x的质因数，而x的质因数一定是n的质因数
——>因此，从小到大遍历数n的因数，并且每次都除尽，那么只会遍历到数n的质因数，而不会是合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//O(sqrt(n))优化
private static void divide(int n)
{
    for(int i = 2; i <= n/i; i++)
    {
        if(n % i == 0)
        {
            int k = 0;
            while(n % i == 0)
            {
                n /= i;
                k++;
            }
            System.out.println(i + " " + k);
        }
    }
    if(n > 1) System.out.println(n + " " + 1);
}

算术基本定理：一个合数可以由多个质因数相乘而得
——> 大于根号n的质因数只有一个
反证法：如果两个大于n的质因数相乘就会超过n
——> 将遍历的范围缩小到根号n，最后要特判一下n是否大于1，如果大于1,那么剩下的n就是最后一个大于根号n的质因数

Count GCD

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
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 2e5 + 10;
const ll mod = 998244353;

void deer()
{
    ll n, m, a[N];
    bool flag = 1;
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
        if (i > 1 && a[i - 1] % a[i] != 0)   flag = 0;
    }
    if (!flag)
    {
        cout << 0 << "\n";
        return;
    }
    ll ans = 1;
    for (int i = 2;i <= n;i++)
    {
        ll d = a[i - 1] / a[i], x = m / a[i], y = 0;//y表示不互质的个数
        //求出[1,x]中与d互质的数的数目
        vector<ll> num;
        for (int i = 2;i * i <= d;i++)  //分解质因数
        {
            if (d % i == 0) //非互质因数
            {
                int len = num.size();
                for (int j = 0;j < len;j++)  num.push_back(-num[j] * i);    //容斥
                num.push_back(i);
                while (d % i == 0)   d /= i;
            }
        }
        if (d > 1)  //特判
        {
            int len = num.size();
            for (int j = 0;j < len;j++)  num.push_back(-num[j] * d);
            num.push_back(d);
        }
        for (ll i : num)   y += x / i;
        ans = ans * (x - y) % mod;
    }
    cout << ans << "\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--)
    {
        deer();
    }

    return 0;
}