A*B Problem（模9取余法）

2019-04-13 13:19发布

站内文章 / 模拟电子
10202 0 1047
描述 设计一个程序求出A*B，然后将其结果每一位相加得到C，如果C的位数大于等于2，继续将C的各位数相加，直到结果是个一位数k。 例如： 6*8=48； 4+8=12； 1+2=3； 输出3即可。 输入 第一行输入一个数N(0 随后的N行每行给出两个非负整数m，n（0<=m,n<=10^12)。 输出 对于每一行数据，输出k。 样例输入 3 6 8 1234567 67 454 1232 样例输出 3 4 5 补充四个初等数论知识： 1，(a+b)%n=(a%n+b%n)%n; 2，(a-b)%n=(a%n-b%n+n)%n; 3，(a*b)%n=(a%n*b%n)%n; 4，k*(10^M)%9=k; 对于一个整数n,设f(n)为n的各个位之和，有这样一个等式 n%9=f(n)%9; 用一式个四式 可以证明。还要注意我们所求的是一个一位数，而我们是对9取余的，当余数为0时，我们要的 结果可能是0，可能是9。是0的情况，只有开始时两个乘数至少有一个为0。其他情况为9 #include #include #include using namespace std; typedef long long ll; int main() { int t; scanf("%d",&t); while (t--) { ll a,b; scanf("%lld %lld",&a,&b); if (a==0 || b==0) printf("0 "); else { int ans = (a%9)*(b%9)%9; if (ans==0) ans = 9; printf("%d ",ans); } } return 0; }        

热门文章