通过质因子链看数论中的基本问题

例：输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

输入格式
输入包含多组数据，每组数据占一行，包含一个正整数表示 X。

输出格式
对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

每个结果占一行。

数据范围
1≤X≤220
输入样例：
2
3
4
10
100
输出样例：
1 1
1 1
2 1
2 2
4 6

求最大公约数（辗转相除法）

求公约数本题未用到

int gcd(int a, int b){
    //gcd(a, b)表示a和b的最大公约数，0和任何数x的最大公约数都是x本身
    return b? gcd(b, a % b) : a;
}

*多重集合的排列数问题

算术基本定理 ：

通过找最小质因子来得到需要拆分后的数：p -> p / p1 (p1为p的最小质因子) p / p1 -> p / p1/p2(p2为p / p1的最小质因子)

X = p1^α1 * p2^α2 * p3^α3 ... pk^αk

多重集合的排列数问题：

(α1 + α2 + α3 +...+ αk )!/ α1!α2!α3!...αk!

总数全排列，列出所有的情况；再除以相同的数的全排列，去掉相同的情况

本题问题的等价：找出满足的序列个数 <=> 拆分后的数拼接出最大数的种数， 即问α1个p1、α2个p2...αk个pk有多少种拼接成x的情况

*筛素数-线性筛法

可以在O(N)内求1~n的所有质素，以及每个数的最小质因子

int cnt;
int primes[N];
int minp[N];
bool st[N];

int get_primes(int n){
    for(int i =  2; i < n; i++){
        if(!st[i]){
            primes[cnt++] = i;  //没有被筛掉的数就是质数
            minp[i] = i;
        }
        for(int j = 0; primes[j] * i <= n; j++){
            st[primes[j] * i] = true;  //可以写成相乘的形式，不是质数，筛掉
            minp[primes[j] * i] = primes[j];
            if(i % primes[j] == 0)break;  //将i之前的所有质数的i倍数都筛掉，可以防止筛两遍
        }
    }
}

综合上述几种算法本题代码为：

#include
#include
#include
#include

using namespace std;
typedef long long LL;

const int N = (1 << 20) + 10;

int primes[N];
int cnt;
bool st[N];
int minp[N];
    
void get_primes(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            primes[cnt++] = i;
            minp[i] = i;
        }
        for(int j = 0; primes[j] * i <= n; j++){
            st[primes[j] * i] = true;
            minp[primes[j] * i] = primes[j];
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
	get_primes(N - 1);
    int fact[30], sum[N];
    int x;
    while(scanf("%d", &x) != -1){
        int k = 0, tot = 0;
        while(x > 1){
            int p = minp[x];
            fact[k] = p, sum[k] = 0;
            while(x % p == 0){
                x /= p;
                sum[k]++;
                tot++;
            }
            k++;
        }  //将x划分成X = p1^α1 * p2^α2 * p3^α3 ... pk^αk的形式，fact存pi、sum存αi
        
        LL res = 1;
        for(int i = 1; i <= tot; i++) res *= i;
        for(int i = 0; i < k; i++)
            for(int j = 1; j <= sum[i]; j++)
                res /= j;
        printf("%d %lld\n", tot, res);
        
    }

    return 0;
}