[SGU][ACM]118 Digital Root
海胖子 - 2015/02/06题目链接
http://acm.sgu.ru/problem.php?contest=0&problem=118
题目大意
定义f(n)为n各位数字之和,如果n是各位数,则n个数根是f(n),否则为f(n)的数根。
现在给出n个Ai,求出 A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1 这个式子的数根。
题解
定义d(n)为n的数根,利用数学归纳法可证明(从N=1的情况向上递推):
1、d( A1*A2* … *AN ) = d( AN * d( A1*A2* … *AN-1 ) )
2、d(A1 + A2 ) = d( d(A1) +d(A2) )
知识点
数根是自然数的一种性质,换句话说,每个自然数都有一个数根。数根是将一正整数的各个位数相加(即横向相加),若加完后的值大于10的话,则继续将各位数进行横向相加直到其值小于十为止,或是,将一数字重复做数字和,直到其值小于十为止,则所得的值为该数的数根。
例如54817的数根为7,因为5+4+8+1+7=25,25大于10则再加一次,2+5=7,7小于十,则7为54817的数根。
公式法求数根:
a的数根b = ( a - 1) % 9 + 1
另外还有一个结论要记:任何一个整数模9同余于它的各数位上数字之和。
具体证明过程如下:
设自然数N=a[n]a[n-1]…a[0],其中a[0],a[1]、…、a[n]分别是个位、十位、…上的数字
再设M=a[0]+a[1]+…+a[n]
求证:N≡M(mod 9).
证明:
因为 N=a[n]a[n-1]…a[0]=a[n]*10^n+a[n-1]*10^(n-1)+…+a[1]*10+a[0]
又因为 1≡1(mod 9), 10≡1(mod 9), 10^2≡1(mod 9), … 10^n≡1(mod 9)
上面这些同余式两边分别同乘以a[0]、a[1]、a[2]、…、a[n],再相加得:
a[0]+a[1]*10+…+a[n]*10^n≡(a[0]+a[1]+…+a[n])(mod 9), 即 N≡M(mod 9),得证。
代码
// // main.cpp // sgu // // Site @haipz.com // Copyright (c) 2015年 林海鸿. All rights reserved. // #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cfloat> #include <map> #include <queue> #include <vector> #include <algorithm> using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); int ans = 0, t = 1; while (n--) { int a; scanf("%d", &a); t = t*(a % 9) % 9; ans += t; } ans %= 9; if (ans == 0) printf("9\n"); else printf("%d\n", ans); } return 0; }
转载保留版权:http://haipz.com/blog/i/6456 - 海胖博客
顿时觉得你的网站很高端。