Digital Root
Problem's Link
Mean:
定义f(n)为n各位数字之和，如果n是各位数，则n个数根是f(n)，否则为f(n)的数根.
现在给出n个Ai，求出A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1 这个式子的数根.
analyse:
这道题目要用到这个规律，设f(n)是n的digital root，那么f(A*N)=f(A*f(N));
具体证明过程如下：
设自然数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)，得证。
有了这个性质就容易解决本题了
在计算过程中，可以不断mod 9，因为我们知道有这样两个性质：
(A+B)mod C = （(A mod C) + (B mod C)）mod C
(AB)mod C = ((A mod C)×(B mod C)) mod C
还要注意，如果余数为0，则输出9.
Time complexity: O(N)
view code
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
* Author: crazyacking
* Date : 2016-01-08-10.51
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long(LL);
typedef unsigned long long(ULL);
const double eps(1e-8);
#define REP( i, n )
for ( int i = 0; i < (n); i++ )
#define REPD( i, n )
for ( int i = (n) - 1; i >= 0; i-- )
#define FOR( i, b, e )
for ( int i = (b); i <= (e); i++ )
typedef long long int64;
const int MAXN = 1000;
int T, N;
int64 val[MAXN];
int droot( int x )
{
if ( x < 10 ) return x;
int ans = 0;
while ( x > 0 )
{
ans += x % 10;
x /= 10;
}
return droot( ans );
}
int main()
{
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d", &N );
#warning READ LLD
REP( i, N )
scanf( "%I64d", &val[i] );
int64 ans = droot( val[N - 1] );
REPD( i, N - 1 )
ans = droot( droot(val[i]) * droot(ans+1) );
printf( "%I64d ", ans );
}
return 0;
}