2013
11-12

# Interesting Yang Hui Triangle

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

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

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.

3 4
3 48
0 0

Case 1: 0004
Case 2: 0012

/* @author: */
import java.util.Scanner;
public class Main {

static int clac( int s, int p, int n ) {
if( s < p )	return 0;
return (s-n%s-1)*(n/s) + clac( s/p, p, n%s )*((n+s-1)/s);
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n, p, s, k=0, t;
while(sc.hasNext()) {
p=sc.nextInt();
n=sc.nextInt();
if(p==00&&n==0) break;
s = 1;
while( s <= n/p )
s *= p;
t = clac( s, p, n );
System.out.printf( "Case %d: %04d\n", ++k, (n+1-t)%10000 );
}
}
}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

3. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。

4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.