CodeForces 396A 數論 組合數學

CodeForces 396A 數論 組合數學

 

好久沒做數論的東西了，一個獲取素數的預處理跟素因子分解寫錯了，哭瞎了，呵呵，

首先ai最大值為10^9,n為500,最壞的情況 m最大值為500個10^9相乘，肯定不能獲取m了，首選每一個ai肯定是m的一個因子，然後能分解就把ai給分解素因子，這樣全部的ai都分解了 就能得到m的 所有素因子 以及 所有素因子的個數，題目求的 是n個因子的 不同序列的個數，所以每次 只能選出n個因子，這n個因子由素因子組成，其實就是對應每一個素因子 把它分配在n個位置上有多少種分法，然後所有素因子分法的 乘積就是最終的答案,至於怎麼分配 其實就是隔板法

隔板法裡有個是 允許有空的，這道題也是允許有空的

 

 

例1將20個大小形狀完全相同的小球放入3個不同的盒子，允許有盒子為空，但球必須放完，有多少種不同的方法？ 分析：本題中的小球大小形狀完全相同，故這些小球沒有區別，問題等價於將小球分成三組，允許有若干組無元素，用隔板法. 解析：將20個小球分成三組需要兩塊隔板，因為允許有盒子為空，不符合隔板法的原理，那就人為的再加上3個小球，保證每個盒子都至少分到一個小球，那就符合隔板法的要求了（分完後，再在每組中各去掉一個小球，即滿足了題設的要求）。然後就變成待分小球總數為23個，球中間有22個空檔，需要在這22個空檔裡加入2個隔板來分隔為3份，共有C（22，2）=231種不同的方法. 點評：對n件相同物品（或名額）分給m個人（或位置），允許若干個人（或位置）為空的問題,可以看成將這n件物品分成m組，允許若干組為空的問題.將n件物品分成m組，需要m-1塊隔板，將這n件物品和m-1塊隔板排成一排，占n+m-1位置，從這n+m-1個位置中選m-1個位置放隔板，因隔板無差別，故隔板之間無序，是組合問題，故隔板有Cn+m-1 m-1種不同的方法，再將物品放入其余位置，因物品相同無差別，故物品之間無順序，是組合問題，只有1種放法，根據分步計數原理，共有Cn+m-1 m-1×1=Cn+m-1 m-1種排法

 

假設素因子p有 k個，那麼分法就是 C[K + N - 1][N - 1]，累積就可以了

 

 

 

const ll MOD = 1000000007;

int n;

map mp;

map ::iterator it;

const int MAXN = 15000;

int C[MAXN + 1][500 + 1];//m最大大概為x * 10^4500左右，所以大概需要2^15000

void Initial() {//組合數
	int i,j;
	for(i=0; i<=MAXN; i++) {
		if(i <= 500)C[0][i] = 0ll;
		C[i][0] = 1ll;
	}
	for(i=1; i<=MAXN; ++i) {
		for(j=1; j<=MAXN && j <= 500; j++)
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
	}
}

#define N 50009

int prime[N];
bool isprime[N];
int nprime = 0;

void make_prime() {//獲取一定范圍內素數
	memset(isprime,false,sizeof(isprime));
	for(int i=2;i<100005 ;i++)
		if(!isprime[i])
			for(int j=i*2;j<100005;j+=i)
				isprime[j]=true;
	for(int i=2;i<100005;i++)
		if(!isprime[i])
			prime[nprime++]=i;
}

void divide(int x) {//素因子分解 
	int temp = (int)sqrt(x * 1.0);
	for(int i=0;i < nprime;i++) {
		if(prime[i] > temp)break;
		while(x%prime[i] == 0) {
			mp[prime[i]]++;
			x /= prime[i];
		}
	}
	if(x != 1)mp[x]++;
}


void init() {
	mp.clear();
}

bool input() {
	while(scanf(%d,&n) == 1) {
		return false;
	}
	return true;
}

void cal() {
	for(int i=0;isecond;
		//int xx = C[tmp + n - 1][n - 1];
		//int yy = C[1][0];
		ans = (ans %MOD * C[tmp + n - 1][n - 1]%MOD)%MOD;
	}
	cout<