## [整理]ACM模拟题详解（2）——简单数论 杰拉斯 | 时间：2012-02-17, Fri | 7,838 views

## 1、Self Numbers

Description

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), .... For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97.

Input

No input for this problem.

Output

Write a program to output all positive self-numbers less than 10000 in increasing order, one per line.

Sample Input

Sample Output

`1`
`3`
`5`
`7`
`9`
`20`
`31`
`42`
`53`
`64`
` |`
` |       <-- a lot more numbers`
` |`
`9903`
`9914`
`9925`
`9927`
`9938`
`9949`
`9960`
`9971`
`9982`
`9993`

d(123) = 123+1+2+3=129

d(55)=55+5+5=65

`这里把x1x2…xn称为y的生成子，例如123是129的生成子，55是65的生成子。题目要求列出10000以内没有生成子的整数。`

```public static void setNumbers(){
int[] numbers=new int;
Arrays.fill(numbers, 0);
for(int i=1;i<10000;i++){
int temp = i+i%10+(i/10)%10+(i/100)%10+i/1000;
if(temp<10000)
numbers[temp-1]=1;
}
for(int i=0;i<9999;i++){
if(numbers[i]==0)
System.out.println(i+1);
}
}
```

## 2、Goldbach's Conjecture

Description

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:

Every even number greater than 4 can be written as the sum of two odd prime numbers.

For example:

8 = 3 + 5. Both 3 and 5 are odd prime numbers.
20 = 3 + 17 = 7 + 13.
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)

Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.

Input

The input will contain one or more test cases.Each test case consists of one even integer n with 6 <= n < 1000000. Input will be terminated by a value of 0 for n.

Output

For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."

Sample Input

`8`
`20`
`42`
`0`

Sample Output

`8 = 3 + 5`
`20 = 3 + 17`
`42 = 5 + 37`

42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23

```/*
* 8 = 3 + 5
* 20 = 3 + 17
* 42 = 5 + 37
*/
public static void test(int x){
if(6<=x && x < 1000000){
if(x%2!=0){
System.out.println("输入数据不是偶数！");
}else{
boolean b=false;
for(int i=3;i+i<x;i++){
if(isPrime(i) && isPrime(x-i)){
System.out.println(x+" = "+i+" + "+(x-i));
b = true;
break;
}
}
if(!b)
System.out.println("Goldbach's conjecture is wrong.");
}
}else{
System.out.println("输入数据范围不对");
}
}

/*
* 判断某个数是否为质数，如果是返回true
*/
public static boolean isPrime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0)
return false;
}
return true;
}
```

## 3、Sum of Consecutive Prime Numbers

Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20. Your mission is to write a program that reports the number of representations for the given positive integer.

Input

The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.

Output

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.

Sample Input

`2`
`3`
`17`
`41`
`20`
`666`
`12`
`53`
`0`
`Sample Output`
`1`
`1`
`2`
`3`
`0`
`0`
`1`
`2`

```/*
* Sum of Consecutive Prime Numbers
*/
public static int test2(int x){
int count=0;
for(int i=2;i+i<x;i++){
int sum = 0;
if(!isPrime(i)){
continue;
}
for(int j=i;j<x;j++){
// 判断是否为质数
if(!isPrime(j))
continue;
sum = sum+j;
// 判断是否满足条件
if(sum>=x){
if(sum==x){
count++;
}
break;
}
}
}
if(isPrime(x))
count++;
return count;
}

/*
* 判断某个数是否为质数，如果是返回true
*/
public static boolean isPrime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0)
return false;
}
return true;
}
```

## 4、Binomial Coefficients

Description

The binomial coefficient

C

(

n

k

) has been extensively studied for its importance in combinatorics. Binomial coefficients can be recursively defined as follows:

C

(

n

, 0) =

C

(

n

n

) = 1 for all

n

> 0;

C

(

n

k

) =

C

(

n

− 1,

k

− 1) +

C

(

n

− 1,

k

) for all 0 <

k

n

.

Given

n

and

k

, you are to determine the parity of

C

(

n

k

).

Input

The input contains multiple test cases. Each test case consists of a pair of integers

n

and

k

(0 ≤

k

≤

n

< 231

n

> 0) on a separate line.

End of file (EOF) indicates the end of input.

Output

For each test case, output one line containing either a “`0`” or a “`1`”, which is the remainder of

C

(

n

k

) divided by two.

Sample Input

`1 1`
`1 0`
`2 1`

Sample Output

`1`
`1`
`0`

C

(

n

k

)满足下面的要求：

C

(

n

, 0) =

C

(

n

n

) = 1 for all

n

> 0;

C

(

n

k

) =

C

(

n

− 1,

k

− 1) +

C

(

n

− 1,

k

) for all 0 <

k

n

.

k

≤

n

< 231

n

> 0)计算C(n,k)，典型的递归问题。但是如果采用递归，当n的值比较大的时候，会堆栈益处。而上面的表达式应该有相应的公式。如果采用公式计算就会变的简单了。公式自己找吧。