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=;

        for (int i=;i<n;i++)

            sum=(sum*x)%;

        if (sum==)

            printf("9\n");

        else

            printf("%lld\n",sum);

    }

    return ;

}

数论

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

巴特西

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

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

Problem Description

Input

Output

Sample Input

Sample Output

Source

最新文章

热门文章

巴特西

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

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

Problem Description

Input

Output

Sample Input

Sample Output

Source

最新文章

热门文章

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