Poj3421 X-factor Chains 质因数分解 组合计数

一道组合计数题 题意:给定一个正整数X, 一个长度为m的X-因子链是由m+1个整数组成的。

其中 1 = X0, X1, X2, …, Xm = X 满足Xi < Xi+1 且 Xi 整除 Xi+1 。

现在要求X-因子链的最大长度和最大长度有多少条？

分析:一条最长链里面,要求是 X i + 1 X_i+1 Xi​+1 % X i X_i Xi​ ==0 且 X i + 1 X_i+1 Xi​+1 > X i X_i Xi​. 我们不难想到 X i + 1 X_i+1 Xi​+1是 X i X_i Xi​乘上某个素数因子得到的.进一步地,如果想要让这个链的长度最大,那么唯一分解出来的每个素数因子和指数都要用上,用例子表达更加形象. 以 100 100 100为例子,进行唯一分解,把它分解为若干个素数指数相乘的形式. 100 = 2 2 ∗ 5 2 100 = 2^2 * 5 ^2 100=22∗52 最长链有 1 − 2 − 4 − 20 − 100 , 1 − 2 − 10 − 20 − 100 , 1 − 5 − 10 − 50 − 100 , 1 − 5 − 25 − 50 − 100. 共 计 四 种 , 长 度 是 4 （ 不 含 1 ） 1 - 2 - 4 - 20 -100,1-2 - 10 -20 -100, 1-5- 10- 50 -100,1- 5 -25-50 - 100.共计四种,长度是4（不含1） 1−2−4−20−100,1−2−10−20−100,1−5−10−50−100,1−5−25−50−100.共计四种,长度是4（不含1）. 不难发现,答案的长度就是每个素数分解出来的指数相加，也就是 X = p 1 a 1 ∗ p 2 a 2 ∗ p 3 a 3 ∗ … ∗ p n a n X = {p1} ^ {a1} *{p2}^{a2}*p3^{a3}*\ldots*{pn}^{an} X=p1a1∗p2a2∗p3a3∗…∗pnan. 该链的最长长度就是 ∑ i = 1 n a i \sum_{i=1}^{n} {a_i} ∑i=1n​ai​.那么最长链有多少种呢,事实上就是高中的组合计数问题了,现在你有n种素数,每种素数有 a i a_i ai​个.假设最长链的长度是m.你的目标是往m个横线里入这全部的素数,有多少种组合方式.

如果现在有M条横线.现在我们想先放置第i个素数,把它放到 a i ai ai个横线里面去，方案数是 C(M,ai).好了ai条横线用完,还剩余下M-ai条横线. 每个素数放置是乘法原理,应当相乘. 故答案为 ∏ i = 1 n C ( M , a i ) ∣ ∣ M = m , m − = a i \prod_{i=1}^{n} C(M,ai)||{M=m,m-=ai} ∏i=1n​C(M,ai)∣∣M=m,m−=ai 至于如何分解质因数,本题可以暴力打个素数表挨个找,因为数据弱. 我直接套用了Pollard-Rho. AC代码:

/*
*/
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 3e5+2;
const int INF = 1e9+7;
const ll MOD = 1e18;
	int prime[10]={2,3,5,7,11,13,19,61,29,37};
struct Prime{
	ll f_mul(ll x,ll y,ll mod){
    return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;
	}
	ll f_pow(ll a,ll b,ll mod){
	ll ans = 1;
	while(b){
		if(b&1) ans= f_mul(ans,a,mod);
		b>>=1;a = f_mul(a,a,mod);
	}
	return ans%mod;
}
	ll gcd(ll a,ll b){
		if(b==0) return a;
		return gcd(b,a%b);
	}
	bool check(ll p,ll x){
		// to check  whether x is a prime.
		if(x % p ==0) return false;
		ll k = x - 1;
		ll t = f_pow(p%x,k,x);
		if(t!=1) return false;
		while(!(k&1)){ //一直到 k不是奇数为止 
			t = f_pow(p,k>>=1,x);
			if(t!=1&&t!=x-1) return false;
			if(t==x-1) return true;// t =x -1 而不是1的情况下 不能继续套用二次探索
			// 因为 x ^2  ≡1 是二次探索的右边 这时候右边是 x - 1 不能继续用了 认为通过测试. 
		}
		return true;
	}
	bool Miller_Rabin(ll x){
		for(int i=0;i=0 ? x : (-x) ;
	}
    ll dfs(ll n){
    	ll x1 = 0 , x2 =0, c= rand()%(n-1) + 1;
    	ll val = 1;
    	for(ll i=1;;ix){
		p.div.clear();p.cnt.clear();
		ll ans1=0,ans2=1;
		//pollard - rho 分解数x 
		p.pollard(x,ans1);
		map &cnt = p.cnt;
		ll m = ans1;
		for(map::iterator it = cnt.begin();it!=cnt.end();it++){
			int k = (*it).second;
			ans2*=(C(m,k));
			m-=k;
		}
		cout