0

In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. nCk denotes the number of ways of choosing k objects from n different objects.

However when n and k are too large, we often save them after modulo operation by a prime number P. Please calculate how many binomial coefficients of n become to 0 after modulo by P.

Input

The first of input is an integer T, the number of test cases.

Each of the following T lines contains 2 integers, n and prime P.

Output

For each test case, output a line contains the number of nCk (0<=k<=n) each of which after modulo operation by P is 0.

Sample Input

3

2 2

3 2

4 3

Sample Output

1

0

1

Since the constraints are very big, dynamic programming will not work. All I want is an idea.

4

2 に答える 2

0

数学に関する問題です。

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Solution{
public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int T=Integer.parseInt(scan.nextLine());
    int i,j;
    long p;
    long y;
    int[] digit=new int[501];
    int[] odigit=new int[501];
    int[] res=new int[501];
    int[] ans=new int[501];
    while(0!=(T--)){
        String[] line=scan.nextLine().split(" ");
        p=Integer.parseInt(line[1]);
        for(i=0;i<line[0].length();i++)
            digit[i+1]=odigit[i]=(line[0].charAt(i))-48;
        digit[0]=odigit[0]=line[0].length()+1;
        //基转换
        //进制转换，10进制转换成p进制
        res[0]=0;
        while(digit[0]>1){
            y=0;i=1;
            ans[0]=digit[0];
            while(i<digit[0]){
                y=y*10+digit[i];
                ans[i++]=(int)((double)y/(double)p);
                y%=p;
            }
            res[++res[0]]=(int)y;
            i=1;
            while(i<ans[0]&&ans[i]==0)
                i++;
            digit[0]=1;
            for(j=i;j<ans[0];j++)
                digit[digit[0]++]=ans[j];
        }
        res[0]++;
        //大数相乘
        BigInteger odata=new BigInteger(line[0]);
        BigInteger pdata=new BigInteger("1");
        for(i=1;i<res[0];i++)
            pdata=pdata.multiply(new BigInteger((res[i]+1)+""));
        odata=odata.subtract(pdata).add(new BigInteger("1"));
        System.out.println(odata.toString());
    }
}
}

EDIT（nhahtdhによるコード短縮）：

import java.math.BigInteger;
import java.util.*;

class Solution {

  // Get the base b intepretation of n
  private static ArrayList<Integer> toBase(BigInteger n, BigInteger b) {
    ArrayList<Integer> out = new ArrayList<Integer>();

    while (!n.equals(BigInteger.ZERO)) {
      out.add(n.mod(b).intValue());
      n = n.divide(b);
    }

    return out;
  }

  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int T = scan.nextInt();

    while((T--) > 0){
      BigInteger n = scan.nextBigInteger();
      BigInteger p = scan.nextBigInteger();

      ArrayList<Integer> res = toBase(n, p);

      BigInteger pdata = BigInteger.ONE;
      for (int i: res) {
        pdata = pdata.multiply(BigInteger.valueOf(i + 1));
      }

      BigInteger output = n.subtract(pdata).add(BigInteger.ONE);

      System.out.println(output);
    }
  }
}
于 2012-09-23T03:08:08.510 に答える
0

ルーカスの定理のページから引用：

二項係数 \tbinom{m}{n} が素数 p で割り切れるのは、n の基数 p の数字の少なくとも 1 つが m の対応する数字より大きい場合に限られます。

于 2016-02-05T16:56:51.963 に答える