Interesting Yang Yui Triangle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 332 Accepted Submission(s): 199

Problem Description

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.

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

......

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 exactly i 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.

Input

There are multiple test cases in the input file. Each test case contains two numbers P and N , (P < 1000, N<=10^9) , where P 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.

Output

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

Sample Input

3 4

      3 48 

0 0

Sample Output

      Case 1: 0004 

      Case 2: 0012 

      思路：lucas定理； 

      要求是p的倍数，那么那个数模p为0。 

      lucas定理为C(n,m)=C(n%p,m%p)*C(n/p,m/p)；所以在递归的过程中如果当前C（n%p,m%p）所取得值不能为0，也就是n%p的值要大于或等于m%p的值，那么可能取值的个数sum*（n%p+1）;同时m%p<=n%p也保证了所取得数小于原来底数。 

1 #include 
         2 #include 
          3 #include 
           4 #include 
            5 #include 
             6 #include 
              7 #include 
 8 #include 
                9 #include 
                10 #include
                 11 using namespace std;12 typedef long long LL;13 int main(void)14 {15 LL p,N;16 int __ca=0;17 while(scanf("%lld %lld",&p,&N),p!=0||N!=0)18 {19 LL sum=1;20 while(N)21 {22 int mod=N%p;23 sum*=mod+1;24 sum%=10000;25 N/=p;26 }printf("Case %d: ",++__ca);27 printf("%04d\n",sum);28 }29 return 0;30 }
 

转载于:https://www.cnblogs.com/zzuli2sjy/p/5733738.html

你可能感兴趣的文章