Pro.ID22260 TitleCasting Out Nines Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22260 AC0 Submit0 Ratio- 时间&空间限制描述You must have heard of the great mathematician Leonardo da Pisa Fibonacci (1170-1240). Among the many algorithms that he described in his Liber Abaci book, (which was first published in 1202,) Fibonacci described the Casting Out Nines procedure for checking out addition, subtraction, and multiplication. According to historians, the procedure was transmitted to Europe by the Arabs, but was probably developed somewhere on the Indian subcontinent and is therefore sometimes also called "the Hindu check." "Casting out nines" is an elementary check of a multiplication which makes use of the congruence 10x ≥ 1 (mod 9). Remember that when writing x ≥ y (mod z) weˇre actually saying that (x mod z) is equal to (y mod z). Let a, b be natural numbers whose product is c. Let the sums of the digits of these numbers be ÷a,÷b, and ÷c. Then a ≥ ÷a (mod 9), b ≥÷b (mod 9), and c ≥ ÷c (mod 9). Furthermore a⊙b ≥ ÷a⊙÷b (mod 9), and so ÷a ⊙÷b ≥ ÷c (mod 9). So if c and ÷a ⊙÷b are incongruent (mod 9), the multiplication has been done incorrectly. For example, 12345 ⊙ 67890 = 838102050. The sum-of-digits of 12345 and 67890 are 15 and 30, respectively, and the product of these is 450. Similarly, the sum-of-digits of 838102050 is 27. And since 450 ≥ 27 ≥ 0 (mod 9), so the Hindu Check shows agreement. As another example, say someone incorrectly calculates 13579⊙24680 = 334129720. Since ÷a⊙÷b = 25 ⊙ 20 = 500 ≥ 5 (mod 9) whereas ÷c = 31 ≥ 4 (mod 9). So the multiplication is definitely incorrect. The Hindu check can also be used to check on additions, since a + b ≥ ÷a +÷b (mod 9). Write a program that determines if a given addition or multiplication passes the Hindu Check or not. 输入Your program will be tested on one or more test cases. Each test case is specified on a separate input line. Each line is of the form: a+b=c. Or, a*b=c. Notice the '.' at the end of the line. 'a', 'b', and 'c' are natural numbers. There are no spaces between the numbers and the symbols ( '+' , '*' , '=' , and '.' ,) but trailing white-space may appear after the '.' . The last line of the input file, which is not part of the test cases, will have a single '.' . 输出Description You must have heard of the great mathematician Leonardo da Pisa Fibonacci (1170-1240). Among the many algorithms that he described in his Liber Abaci book, (which was first published in 1202,) Fibonacci described the Casting Out Nines procedure for checking out addition, subtraction, and multiplication. According to historians, the procedure was transmitted to Europe by the Arabs, but was probably developed somewhere on the Indian subcontinent and is therefore sometimes also called "the Hindu check." "Casting out nines" is an elementary check of a multiplication which makes use of the congruence 10x ≥ 1 (mod 9). Remember that when writing x ≥ y (mod z) weˇre actually saying that (x mod z) is equal to (y mod z). Let a, b be natural numbers whose product is c. Let the sums of the digits of these numbers be ÷a,÷b, and ÷c. Then a ≥ ÷a (mod 9), b ≥÷b (mod 9), and c ≥ ÷c (mod 9). Furthermore a⊙b ≥ ÷a⊙÷b (mod 9), and so ÷a ⊙÷b ≥ ÷c (mod 9). So if c and ÷a ⊙÷b are incongruent (mod 9), the multiplication has been done incorrectly. For example, 12345 ⊙ 67890 = 838102050. The sum-of-digits of 12345 and 67890 are 15 and 30, respectively, and the product of these is 450. Similarly, the sum-of-digits of 838102050 is 27. And since 450 ≥ 27 ≥ 0 (mod 9), so the Hindu Check shows agreement. As another example, say someone incorrectly calculates 13579⊙24680 = 334129720. Since ÷a⊙÷b = 25 ⊙ 20 = 500 ≥ 5 (mod 9) whereas ÷c = 31 ≥ 4 (mod 9). So the multiplication is definitely incorrect. The Hindu check can also be used to check on additions, since a + b ≥ ÷a +÷b (mod 9). Write a program that determines if a given addition or multiplication passes the Hindu Check or not. Input Your program will be tested on one or more test cases. Each test case is specified on a separate input line. Each line is of the form: a+b=c. Or, a*b=c. Notice the '.' at the end of the line. 'a', 'b', and 'c' are natural numbers. There are no spaces between the numbers and the symbols ( '+' , '*' , '=' , and '.' ,) but trailing white-space may appear after the '.' . The last line of the input file, which is not part of the test cases, will have a single '.' . Output For each test case, output the result on a single line using the following format: k. result Where k is the test case number (starting at 1,) and result is "PASS" if the addition or multiplication operation of this test case passes the Hindu Check. Otherwise, result is "NOT!" . Sample Input 12345*67890=838102050. 13579*24680=334129720. 23+11=34. . Sample Output 1. PASS 2. NOT! 3. PASS Source 样例输入12345*67890=838102050. 13579*24680=334129720. 23+11=34. . 样例输出1. PASS 2. NOT! 3. PASS 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 18:46 , Processed in 0.035603 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
