首页 > 代码库 > NKOJ1236 a^b (数论定理的应用)

NKOJ1236 a^b (数论定理的应用)

                                                                          a^b

对于任意两个正整数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的余数
证明:
s = a1a2...an = a1*10^(n-1)+a2*10^(n-1)+...+an
              = a1*(999..9+1)+a2*(999..9+1)+...+an
              =(a1*999..9+a2*999..9+...+a(n-1)*9)+(a1+a2+...+an) 
因为:
    (a1*999..9+a2*999..9+...+a(n-1)*9)%9 = 0;

所以:
    s%9=(a1+a2+...+an)%9;
 

代码如下:

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int power(int a,int b)    // 快速幂求余
 5 {
 6     a %=9;
 7     int ans = 1;
 8     while(b>0)
 9     {
10         if(b%2==1)
11             ans=(ans*a)%9;
12         b=b/2;
13         a=(a*a)%9;
14     }
15     return  ans;
16 }
17 int main()
18 {
19     int a,b;
20     while(cin>>a>>b)
21     {
22         if(a==0&&b==0)
23             break;
24         int angs = power(a,b);
25         if(angs==0)
26             cout<<"9"<<endl;
27         else
28             cout<<angs<<endl;
29     }
30     return 0;
31 }

 

NKOJ1236 a^b (数论定理的应用)