题目大意，从1到N，1 = X0, X1, X2, …, Xm = X中间可以分成很多数，另Xi < Xi+1 Xi 可以整除Xi+1 ，求最大长度m和m长度的链有多少条
思路：
很简单，只要把数分解质因数就可以了，最后链条的长度为质因数的个数，组合数为质因数个数的阶乘除以各自重复质因数的阶乘。还记得我发过的GCM和LCM反转的那道题吗，可以用pallord_rho算法分解质因数。
贴代码，第一个是最坑爹的，这一题会专门出数据坑Miller_Rabin算法，所以必须素数验证必须执行8次以上，不能用srand改变种子，否则你就是在和上帝玩骰子。
#include <iostream>
#include <algorithm>
#include <functional>
#include <time.h> using namespace std;
typedef long long LL_INT; bool Miller_Rabin(const LL_INT);
LL_INT witness(const LL_INT,const LL_INT,const LL_INT);
void Find_Factors(const LL_INT, int *const, const int);
LL_INT Pallord_Rho_Theorem(const LL_INT, const int);
LL_INT Multi_Function(LL_INT,const LL_INT);
LL_INT gcd(LL_INT, LL_INT); static LL_INT factors[], factors_num[];
static long long coe[];
static int factors_sum[]; void Inivilize(void)
{
coe[] = ;
for (int i = ; i <= ; i++)
coe[i] = coe[i - ] * i;
} int main(void)
{
LL_INT x;
long long chains_sum;
int prime_sum, len, i; Inivilize();
while (~scanf("%lld", &x))
{
prime_sum = ; len = ;
if (x <= )
printf("0 1\n");
else if (Miller_Rabin(x))//如果是素数，直接返回1 1
printf("1 1\n");
else
{
Find_Factors(x, &prime_sum, );//120是经验值
sort(factors, factors + prime_sum);
factors_num[] = factors[];
memset(factors_sum, , sizeof(factors_sum));
factors_sum[] = ;
for (i = ; i < prime_sum; i++)
{
if (factors[i - ] == factors[i])
factors_sum[len]++;
else
{
factors_num[++len] = factors[i];
factors_sum[len] = ;
}
}
chains_sum = coe[prime_sum];
for (int i = ; i <= len; i++)
chains_sum /= coe[factors_sum[i]];
printf("%d %lld\n", prime_sum, chains_sum);
}
}
return ;
} bool Miller_Rabin(const LL_INT n)
{
if (n == )
return true;//如果是2，就不用判断了
else
{
for (int i = ; i < ; i++)
{
if (!(witness((LL_INT)(rand() % (n - )) + , n - , n) == ))
return false;
}
return true;
}
} LL_INT witness(const LL_INT coe, const LL_INT level, const LL_INT n)
{
LL_INT y, x;
if (level == )
return ;
x = witness(coe, level >> , n); if (x == )
return ;
y = (x*x) % n;
if (y == && x != && x != n - )
return ;//费马小定理的运用
if (level % == )
y = (coe*y) % n; return y;
} void Find_Factors(const LL_INT n, int *const len, const int times)
{
if (n == )
return;
else if (Miller_Rabin(n))
factors[(*len)++] = n;
else
{
LL_INT p = n;
int c = times;
while (p >= n)
p = Pallord_Rho_Theorem(n, c--);
Find_Factors(p, len, times);
Find_Factors(n / p, len, times);
}
} LL_INT Pallord_Rho_Theorem(const LL_INT n, const int c)
{
LL_INT x, y, k = , d;
x = y = rand() % n;//随意取一个随机数 for (int i = ;; i++)
{
x = (Multi_Function(x, n) + c) % n;
d = gcd(n, (y - x + n) % n);//计算|y-x|与n的最大公因数
if ( < d && d < n)
return d;
else if (y == x)
return n;//相当于这个因数分解是失败的，所以直接返回n让外层循环继续
else if (i == k)//brent判据，目的就是找到在偶数周期内找到gcd(x(k)-x(i/2))
{
y = x;//重新y=x,定义循环
k <<= ;
}
}
return n;
} LL_INT Multi_Function(LL_INT x,const LL_INT mod)
{
LL_INT y = x, ans = ;
while (y)//计算y=x^2的取模算法
{
if (y & )
ans = (ans + x) % mod;
x = (x << ) % mod;
y >>= ;
}
return ans;
} LL_INT gcd(LL_INT a, LL_INT b)
{
if (b == )
return a;
return gcd(b, a%b);
}
挺慢的，其实直接用筛法更快，先把表打好，然后再一个一个选就可以了，用筛法的话可以到100ms以内
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; static bool primes[( << ) + ];
static int primes_set[];
static long long fact[]; void Inivilize(int *const primes_sum)
{
int i, j;
primes[] = primes[] = ;
for (i = ; i <= << ; i++)
{
if (!primes[i]) primes_set[(*primes_sum)++] = i;
for (j = ; j*i <= << && j <= i; j++)
{
if (primes[j] == )
primes[j*i] = ;
}
}
fact[] = ;
for (i = ; i <= ; i++)
fact[i] = fact[i - ] * i;
} int main(void)
{
int x, last, i, tmp_div_sum, tmp_last, longest_length, primes_sum = , prime_num;
long long div_sum, chain_sum;
Inivilize(&primes_sum); while (~scanf("%d", &x))
{
if (x == )
printf("0 1\n");
else
{
div_sum = ; last = x; longest_length = ;
for (i = ; last != ; i++)
{
if (!primes[last])
{
longest_length++;
break;
}
prime_num = primes_set[i];
for (tmp_div_sum = , tmp_last = last; tmp_last%prime_num == ;)
{
if (!tmp_last) break;
tmp_last /= prime_num;
tmp_div_sum++; longest_length++;
}
last = tmp_last;
if (tmp_div_sum)
div_sum *= fact[tmp_div_sum];
}
chain_sum = fact[longest_length];
chain_sum /= div_sum;
printf("%d %lld\n", longest_length, chain_sum);
}
}
return ;
}
