Problem 1057 a^b(数论)

Problem Description

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

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();
  }
 }
}