0

在数学中，二项式系数是一系列正整数，在二项式定理中作为系数出现。nCk 表示从 n 个不同对象中选择 k 个对象的方法的数量。

但是当n和k太大的时候，我们经常在对一个素数P进行模运算后保存。请计算n有多少个二项式系数在对P进行模运算后变为0。

输入

第一个输入是一个整数 T，即测试用例的数量。

以下 T 行中的每一行都包含 2 个整数，n 和素数 P。

输出

对于每个测试用例，输出一行包含 nCk (0<=k<=n) 的数量，每个 nCk 经 P 模运算后为 0。

样本输入

3

2 2

3 2

4 3

样本输出

1

0

1

由于约束非常大，动态规划将不起作用。我想要的只是一个想法。

4

2 回答 2

0

This is a problem about math.

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 (code shorten by 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 位中至少有一个大于 m 的相应位。

于 2016-02-05T16:56:51.963 回答