Problem 1057 a^b(数论)

2019-04-13 21:29发布生成海报

站内文章 / 模拟电子

12009 0

Problem Description

对于任意两个正整数a,b（0<=a,b<10000）计算ab各位数字的和的各位数字的和的各位数字的和的各位数字的和。

Input

输入有多组数据，每组只有一行，包含两个正整数a,b。最后一组a=0,b=0表示输入结束，不需要处理。

Output

对于每组输入数据，输出ab各位数字的和的各位数字的和的各位数字的和的各位数字的和。

Sample Input

2 3 5 7 0 0

Sample Output

8 5
这题的目的只是想把最后的结果压到一位数，只存在9种解。由于任何数除以9的余数等于各位数的和除以9的余数。
假设一个数的各位数字分别是a1,a2...an ,则 (a1a2...an)%9=(a1+a2+...+an)%9
证明:
令s=a1a2...an=a1*10^(n-1)+a2*10^(n-2)+...+an
=a1*(999..9+1)+a2*(99..9+1)+...+a(n-1)*(9+1)+an
=(a1*999..9+a2*999..9+...+a(n-1))+(a1+a2+...+an)
s%9=(a1+a2+...+an)%9

所以此题无论求多少次和，除以9的余数是不变的，到一位数的时候就是最
终的余数了。于是问题转化为了求a^b除以9的余数（如果余数为零则答案为9）。

代码如下：

import java.util.Scanner;

public class Fzu1057 {

	
	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);
		int a = s.nextInt();
		int b = s.nextInt();
		int mod;
		while(a!=0&&b!=0)
		{
			mod =1;
			/*a^b=a*a*a*..(b个a相乘)
			 * a^b%9=(a*a*a*a*...)%9=a%9*a%9*a%9...
			*/
			for(int i=1;i<=b;i++)
			{
				mod = (mod*a)%9;
			}
			if(mod==0)
				mod=9;
			System.out.println(mod);
			a = s.nextInt();
			b = s.nextInt();
		}
	}
}