Codeforces 396A 数论,组合数学

题意:给一个a数组,求b 数组的方案数,但是要求两者乘积相同。

分析:

不可能将它们乘起来,对于每个数质因数分解,得到每个质因子个数,遍历这些质因子,将某个质因子放到 对应的盒子里面,可以不放,方案数就是一个组合数,用插板法。

这里的素数板子挺好的,一方面可以用来判断,一方面存起来。

组合数,可以考虑用乘法逆元。

每个质因子个数hash一下。

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + ;
#define N 50009
typedef long long ll; const int maxnn = +;
int C[maxnn][]; void init() {
memset(C, , sizeof(C));
C[][] = ;
C[][] = C[][] = ;
for(int i = ; i < maxnn; ++i)
{
C[i][] = C[i][i] = ;
for(int j = ; j < i; ++j)
{
C[i][j] = (C[i-][j-] + C[i-][j]) % MOD;
}
}
} bool vis[];
int primes[];
int num_prime;
int get_primes (int m) { //获取一定范围内的素数
memset(vis,,sizeof(vis));
for(int i=;i<m;i++) {
if(!vis[i])
primes[num_prime++]=i;
for(int j=;j<num_prime && i*primes[j]<m;j++) {
vis[i*primes[j]]=;
if(!(i%primes[j]))
break;
}
}
return num_prime;
} std::map<int, int> mp; void divide(int x) {
int temp = (int)sqrt(x*1.0);
for(int i=;i<num_prime;i++) {
if(primes[i]>temp) break;
while(x%primes[i]==) {
mp[primes[i]]++;
x /=primes[i];
}
}
if(x!=)
mp[x]++;
} int main(int argc, char const *argv[])
{
mp.clear();
init();
get_primes(N);
int n,x;
scanf("%d",&n);
for(int i=;i<n;i++) {
scanf("%d",&x);
divide(x);
} ll ans= ;
std::map<int, int> ::iterator p; for(p = mp.begin();p!=mp.end();p++) {
int k = p->second; ans = ans * C[k+n-][n-] % MOD;
} printf("%lld\n", ans); return ;
}
上一篇:2015最新百度搜索引擎(seo优化)排名算法


下一篇:路由选择(codevs 1062)