ACMシミュレーション問題の詳細(2)——簡単な数論
数字に関する問題がたくさんあって、主に基本的なプログラミング能力を考察して、数学が比較的に良いならば、これらの問題を解決するのに比較的に良い助けがあります.次のテーマは学生が集めたテーマで、説明しました.
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
问题补充:このような公式y=d(x 1 x 2...xn)=x 1+x 2+...+xn+x 1 x 2...xnがあって、例えば:
d(123) = 123+1+2+3=129
d(55)=55+5+5=65
1から10000までの生成子を遍歴して、どの数字を生成できるかを見て、生成できない出力をすればいいです.以下のコードを参考にします.
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
Sample Output
4より大きい偶数は2つの素数(素数)の和になると推定されます.書き出し式があれば「Goldbach's conjecture is wrong.」と出力するプログラムを作成して検証しましょう.1つ以上書ける式であれば、2つの数字の差が大きいペアを書きます.例:
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23
出力42=5+37でよい.37-5が一番大きいからです.
问题详解:问题は比较的简単で、2つの数が质数であるかどうかをテストすればいい.次のコードを参照してください.
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
一部の整数は複数の連続質量数の和として表すことができ、例えば53=5+7+11+13+17、ある数字は多中表現方法があり、例えば41は2+3+5+7+11+13、11+13+17、and 41と表すことができる.問題は与えられたある数の表示方法を計算することを要求する.
问题详解:与えられた数に対して、まず2から始めて、それから次の质数を探して、それから彼らの和が与えられた数以上になるまで累积して、もし说明が1组の解であるならば、もし说明が接でないならば、それから次の接を探して、终わるまで.次のコードを参照してください.
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 “
Sample Input
Sample Output
二項式係数(翻訳の可能性が低い)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.
問題は与えられたnとk(0≦k≦n<231,n>0)に基づいてC(n,k)を計算することを要求し,典型的な再帰問題である.しかし再帰を採用すると,nの値が比較的大きい場合に利点がスタックされる.上の式には対応する式があるはずです.数式で計算すると簡単になります.公式は自分で探しましょう.
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
135792031425364|| <-- a lot more numbers|9903991499259927993899499960997199829993问题补充:このような公式y=d(x 1 x 2...xn)=x 1+x 2+...+xn+x 1 x 2...xnがあって、例えば:
d(123) = 123+1+2+3=129
d(55)=55+5+5=65
x1x2…xn y ， 123 129 ，55 65 。 10000 。1から10000までの生成子を遍歴して、どの数字を生成できるかを見て、生成できない出力をすればいいです.以下のコードを参考にします.
public static void setNumbers(){ int[] numbers=new int[10000]; 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
820420Sample Output
8 = 3 + 520 = 3 + 1742 = 5 + 374より大きい偶数は2つの素数(素数)の和になると推定されます.書き出し式があれば「Goldbach's conjecture is wrong.」と出力するプログラムを作成して検証しましょう.1つ以上書ける式であれば、2つの数字の差が大きいペアを書きます.例:
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23
出力42=5+37でよい.37-5が一番大きいからです.
问题详解:问题は比较的简単で、2つの数が质数であるかどうかをテストすればいい.次のコードを参照してください.
/* * 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
2317412066612530Sample Output11230012一部の整数は複数の連続質量数の和として表すことができ、例えば53=5+7+11+13+17、ある数字は多中表現方法があり、例えば41は2+3+5+7+11+13、11+13+17、and 41と表すことができる.問題は与えられたある数の表示方法を計算することを要求する.
问题详解:与えられた数に対して、まず2から始めて、それから次の质数を探して、それから彼らの和が与えられた数以上になるまで累积して、もし说明が1组の解であるならば、もし说明が接でないならば、それから次の接を探して、终わるまで.次のコードを参照してください.
/* * 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 11 02 1Sample Output
110二項式係数(翻訳の可能性が低い)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.
問題は与えられたnとk(0≦k≦n<231,n>0)に基づいてC(n,k)を計算することを要求し,典型的な再帰問題である.しかし再帰を採用すると,nの値が比較的大きい場合に利点がスタックされる.上の式には対応する式があるはずです.数式で計算すると簡単になります.公式は自分で探しましょう.