x的因子链
题目 X的因子链
思路分析
本题用到这两个数论常用的算法：
算术基本定理 就是因式分解的定理，所有的整数都可以唯一分解成若干个质因子乘积的形式
\(N=P_1^{α1}×P_2^{α2}×…×P_k^{αk}\)，其中 Pi是质数，每一个 \(αi≥0\)
筛法求素数——线性筛法（欧拉筛法）
在O(N)的时间复杂度内，求出来1 ~ n中所有的质数，以及每一个数的最小质因子。
void get_primes(){
for(int i=2;i<=n;i++){
if(!st[i])
primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
/*
因为prime中素数是递增的，所以如果i%prime[j]!=0代表i的最小质因数还没有找到，
即i的最小质因数大于prime[j]
也就是说prime[j]就是i*prime[j]的最小质因数，于是i*prime[j]被它的最小质因数筛掉了
*/
st[primes[j] * i] = true; // 把质数的i倍筛掉
/*
如果当i%prime[j]==0时，代表i的最小质因数是prime[j]，
那么i*prime[j+k](k>0)这个合数的最小质因数就不是prime[j+k]而是prime[j]了
所以i*prime[j+k]应该被prime[j]筛掉，而不是后续的prime[j+k]，于是在此时break
*/
if (i % primes[j] == 0)
break; // 通过最小质因子来筛
}
}
}
① 筛掉的一定是合数，且一定是用其最小质因子筛的
② 合数一定会被筛掉
这样我们就可以把所有质数找出来，而且每个和数只会被最小质因子筛，所以每个和数只会被筛一次，所以整个算法的时间复杂度为O(N)
回归本题
题意有点绕，通俗来讲就是给我们任意一个正整数X，我们可以求一下X所有的约数：d1,d2…dk，
然后我们要从中挑出来一些严格单调递增的数
使得每一项都是它前一项的倍数：a1<a2<…<at (ai|ai+1)
然后问我们可以挑出来的序列的最大长度是多少，以及有多少个满足条件的单调递增的序列？
每一项必然满足：ai+1=ai⋅P(P是倍数且>1)，每一个后一项都等于前一项乘上一个倍数，那么我们要想让整个序列最长的话，要尽可能让倍数最小，最小只能小到质数，因为小到质数就不能再分了，因此就可以用我们上边的算术基本定理了，
假设X分解质因数的结果：\(X=P1^{α1}×P2^{α2}×…×P_k^{αk}\)，我们可以发现一共有 α1+α2+…+αk 个质因子，因此我们每一次后一项要比前一项至少要多一个倍数，每一次的倍数必然是一个质数，必然是在X当中的某一个质因子，所以序列的最大长度就是 α1+α2+…+αk 那么如何求这样序列的个数呢？先做一个映射，我们不存数的本身，我们存数的增量，原序列是a1,a2…at，映射的序列是：a1,a2/a1,a3/a2,……，at/at-1，这两个序列是一一对应的，给我们第一个序列就可以求第二个序列，在第二个序列中每一个数都是X的质因子，因此序列个数就是X所有质因子的排列数。
排列数公式：
也被称为多重集合的排列数问题，这样就避免了重复情况。
我们分解质因数就用线性筛法来解。
代码实现
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = (1 << 20) + 10;
int primes[N], cnt;
int minp[N];
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
minp[i] = i;
primes[cnt ++ ] = i;
}
for (int j = 0; primes[j] * i <= n; j ++ )
{
int t = primes[j] * i;
st[t] = true;
minp[t] = 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 ++ ;
}
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;
}
💬 评论