poj 3146 Lucas定理的使用

Harry is a Junior middle student. He is very interested in the story told by his mathematics teacher about the Yang Hui triangle in the class yesterday. After class he wrote the following numbers to show the triangle our ancestor studied.

He found many interesting things in the above triangle. It is symmetrical, and the first and the last numbers on each line is 1; there are exactlyi numbers on the line i.

Then Harry studied the elements on every line deeply. Of course, his study is comPRehensive.

Now he wanted to count the number of elements which are the multiple of 3 on each line. He found that the numbers of elements which are the multiple of 3 on line 2, 3, 4, 5, 6, 7, … are 0, 0, 2, 1, 0, 4, … So the numbers of elements which are not divided by 3 are 2, 3, 2, 4, 6, 3, …, respectively. But he also found that it was not an easy job to do so with the number of lines increasing. Furthermore, he is not satisfied with the research on the numbers divided only by 3. So he asked you, an erudite expert, to offer him help. Your kind help would be highly appreciated by him.

Since the result may be very large and rather difficult to compute, you only need to tell Harry the last four digits of the result.

There are multiple test cases in the input file. Each test case contains two numbersP and N, (P < 1000, N ≤ 10⁹), whereP is a prime number and N is a positive decimal integer.

P = 0, N = 0 indicates the end of input file and should not be processed by your program.

For each test case, output the last four digits of the number of elements on theN + 1 line on Yang Hui Triangle which can not be divided by P in the format as indicated in the sample output.

3 43 480 0Sample Output
Case 1: 0004Case 2: 0012
题意：杨辉三角第n+1层上能被素数p整除的数的个数
Lucas定理：
对于c(n,m)mod p，用a[k]a[k-1]...a[0]，b[k]b[k-1]...b[0]来分别表示n和m对应的素数p进制数，即
n = a[k]*p^k + a[k-1]*p^(k-1) + ... + a[1]*p + a[0]m = b[k]*p^k + b[k-1]*p^(k-1) + ... + b[1]*p + b[0]
C(n,m)mod p=[C(a[k],b[k])×C(a[k-1],b[k-1])×...×C(a[0],b[0])]mod p
杨辉三角对应着C(n,m)矩阵
if i>=j  c(i,j)!=0
if i<j     c(i,j)=0
对于[C(a[k],b[k])×C(a[k-1],b[k-1])×...×C(a[0],b[0])]mod p！=0的种数，其中由于n确定，所以a[]确定，种数由b[]决定
c(i,j)必须全不为0，才能被p整除
C(n,m)=n*(n-1)*(n-2)*……*(n-m+1)/(1*2*3*……*m) ，a[]和b[]都小于p，无法被p整除
所以每项都要b[i]>=a[i]，0=<i<=k
每一项的个数为(a[i]+1),即b=0~a[i];
总数为(a0+1)(a1+1)......(ak+1);
#include<iostream>#include<cmath>#include<cstring>#include<cstdio>#include<algorithm>#define inf 0x3f3f3f3f#define ll long long#define mod 10000using namespace std;int main(){    int p,n;    int kcase=1;    while(cin>>p>>n)    {        if(p==0&&n==0)            return 0;        int ans=1;        while(n)        {            ans=(ans*(n%p+1))%mod;//原题需要保留4位数字            n=n/p;        }        printf("Case %d: %04d/n",kcase++,ans);    }    return 0;}