输入p n 求杨辉三角的第n+1行不能被p整除的数有多少个

Lucas定理：

A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。

    则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0])  mod p同余

即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)，在存在i。b[i]>a[i]时，mod值为0，所以必然整除。当对于全部i，b[i]<=a[i]时。a[i]!%p!=0,所以必然不能整除

#include <cstdio>

#include <cmath>

#include <cstring>

using namespace std;

int main()

{

    int p, n;

    int cas = 1;

    while(scanf("%d %d", &p, &n) != EOF)

    {

        if(p ==0 && n ==0)

            break;

        int sum = 1;

        while(n)

        {

            sum *= n%p+1;

            n /= p;

        }

        printf("Case %d: %04d\n", cas++, sum%10000);

    }

}