Divisors POJ - 2992
3885 ワード
タイトルリンク
Input
Output
Sample Input
Sample Output
タイトル:
組合せ数の因子個数を求める.
考え方:
結合数を階乗として作成する、各素数因子の個数を集計すればよい.
コスト:
Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?
Input
The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.
Output
For each instance, output a line containing exactly one integer -- the number of distinct divisors of Cnk. For the input instances, this number does not exceed 2 63 - 1.
Sample Input
5 1
6 3
10 4
Sample Output
2
6
16
タイトル:
組合せ数の因子個数を求める.
考え方:
結合数を階乗として作成する、各素数因子の個数を集計すればよい.
コスト:
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 500;
int pri[maxn];
int a[maxn];
int b[maxn];
bool vis[maxn];
int num;
void prime(){
num = 0;
memset(vis, false, sizeof(vis));
for(int i = 2; i < maxn; ++i){
if (!vis[i]) pri[++num] = i;
for(int j = 1; j <= num && i * pri[j] < maxn; ++j){
vis[ i* pri[j]] = true;
if (i % pri[j] == 0) break;
}
}
}
int solve(int n, int t){
int ans = 0;
int x = t;
while(t <= n){
ans += n / t;
t *= x;
}return ans;
}
int main(){
//ios::sync_with_stdio(false);
int n, m;
prime();
while(scanf("%d %d", &m, &n) != EOF){
// if(n > m / 2) n = m - n;
LL ans = 1;
for(int i = 1; i <= num && pri[i] <= m; ++i)
ans *=(solve(m, pri[i]) - solve(n, pri[i]) - solve(m - n, pri[i]) + 1);
printf("%lld
",ans);
}return 0;
}