首页 > 专题系列 > Java解POJ > POJ 2992 Divisors [解题报告] Java
2013
11-12

POJ 2992 Divisors [解题报告] Java

Divisors

问题描述 :

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?

输入:

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.

输出:

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 263 – 1.

样例输入:

5 1
6 3
10 4

样例输出:

2
6
16

解题代码:

//* @author: [email protected]
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int[] prime=new int[]
   {
	2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
	53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,
	127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,
	199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
	283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,
	383,389,397,401,409,419,421,431
   };
   int[] arr=new int[84];
   while(in.hasNext())
   {
	int c=in.nextInt();
	int n=in.nextInt();
	int k=c-n;
	for(int i=0;i< 83;i++)
         arr[i]= cal(c,prime[i])-cal(n,prime[i])-cal(k,prime[i]);
	long ans=1;
	for(int i=0;i< 84;i++)
	  if(arr[i]!=0) ans*=(arr[i]+1);
	System.out.println(ans);
    }
  }

public static int cal(int n, int p) {
     if(n < p) return 0;
     else return n / p + cal(n / p, p);
 }
}