描述
对于任意的两个非负整数a,b(0<=a,b<10000),请计算a^b各位数字的和的各位数字的和……
输入
输入两个非负整数a,b(0<=a,b<10000),注意哦,输入可是多组哦!还有就是最后一组a=0,b=0表示输入结束,不需要处理哦!
输出
对于每组输入的数据,请计算a^b各位数字的和的各位数字的和……
样例输入
2 3
5 7
0 0
样例输出
8
5
提示
注意输入数据的范围和最后结果的范围哦!
题目来源
qingyezhu
题目上传者
qingyezhu
刚看到这题就想把1033里的直接拿过来用,结果WA发现并不是一样的题。。然后第一次↓
#include<stdio.h> int main() { int a,b,i,j,site,ret,sum; while(scanf("%d %d",&a,&b)!=EOF) { &&b==) { break; } ]= {}; site=; ;i<=b;i++) { ;j<=site;j++) temp[j]*=a; ;j<=site;j++) { temp[j+]+=temp[j]/; temp[j]%=; ||temp[site+]>) ++site; } } ret = ; sum = ; while(site--) ret+=temp[site]; ||sum/!=) { sum+=ret%; ret/=; &&sum/!=) { ret = sum; sum = ; } } printf("%d\n",sum); } ; }
超时。
果然ACM这种东西要先学习才行,这时候果断google
assume a1,a2...an ,then (a1a2...an)%9=(a1+a2+...+an)%9 prove: make 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的余数都跟它各位数相加之和除以9的余数相同,递推到最后就可以得知该数的各位数之和之和之和……就是它除以9的余数(且余数为0的时候结果为9)。
又因为(a*a)%9=(a%9*a%9)%9,所以(a*a*a)%9=((a*a)%9*a%9)%9=((a%9*a%9)%9*a%9)%9,即若只使结果相同,则程序可以利用循环带入写成如下形式↓
#include<stdio.h> int main() { int a,b,i,ret; while(scanf("%d %d",&a,&b)!=EOF) { &&b==) break; ,ret=;i<=b;i++) ret = (ret%)*(a%); ret%=; if(ret) printf("%d\n",ret); ) printf("0\n"); else printf("9\n"); } ; }
AC~