FZU 1057 a^b 【数论/九余定理】

Accept: 1164 Submit: 3722
Time Limit: 1000 mSec Memory Limit : 32768 KB

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

Source

FZUPC Warmup 2005

【分析】：前几天刚好发布过一片关于同余运算结论的博客。

1.九余数定理：一个数的每位数字之和等于这个数对9取余，如果等于0就是9

2.假设一个数的各位数字分别是a1,a2...an ,则 (a1a2...an)%9=(a1+a2+...+an)%9

3.计算a^b各位数字的和的各位数字的和的各位数字的和的各位数字的和，可以转化为（a*a*a*...）%9 的结果，又有公式(a*b)%n = ((a%n)*(b%n)) % n;则可以循环的求解。

注意用在线算法，边算边取模，就不会T。就是说一个一个的乘即可，变乘边取模。这里只是针对n不大的情况。如果n太大，利用快速幂即可。

【代码】：

#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<streambuf>
#include<cmath>
#include<string>
using namespace std;
#define ll long long
#define oo 10000000

int x,n;
ll sum;
int main(){
    while (~scanf("%d%d",&x,&n),x&&n){
        sum=1;
        for (int i=0;i<n;i++)
            sum=(sum*x)%9;

        if (sum==0)
            printf("9
");
        else
            printf("%lld
",sum);
    }
    return 0;
}

数论

【同类】：HDU-人见人爱A^B