题目描述 Let $f(n)$ be a sum of digits for positive integer $n$. If $f(n)$ is one-digit number then it is a digital root for $n$ and otherwise digital root of $n$ is equal to digital root of $f(n)$. For example, digital root of $987$ is $6$. Your task is to find digital root for expression $\sum_{i=1}^N \prod_{j=1}^i A_j$.
题意概述 给定一个长度为$N$的数列$A_i$,求$\sum_{i=1}^N \prod_{j=1}^i A_j$的数根。
数据范围:$1 \le N \le 1000, \ 1 \le A_i \le 10^9$。
算法分析 数根有一个有趣的性质:如果$n$等于$0$,那么它的数根就是$0$,否则,它的数根等于$(n-1)%9+1$。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;struct IOManager { template <typename T> inline bool read (T &x) { char c = '\n' ; bool flag = false ; x = 0 ; while (~ c && ! isdigit (c = getchar ()) && c != '-' ) ; c == '-' && (flag = true , c = getchar ()); if (! ~ c) return false ; while (isdigit (c)) x = (x << 3 ) + (x << 1 ) + c - '0' , c = getchar (); return (flag && (x = -x), true ); } inline bool read (char &c) { c = '\n' ; while (~ c && ! (isprint (c = getchar ()) && c != ' ' )) ; return ~ c; } inline int read (char s[]) { char c = '\n' ; int len = 0 ; while (~ c && ! (isprint (c = getchar ()) && c != ' ' )) ; if (! ~ c) return 0 ; while (isprint (c) && c != ' ' ) s[len ++] = c, c = getchar (); return (s[len] = '\0' , len); } template <typename T> inline IOManager operator > (T &x) { read (x); return *this ; } template <typename T> inline void write (T x) { if (x < 0 ) putchar ('-' ), x = -x; if (x > 9 ) write (x / 10 ); putchar (x % 10 + '0' ); } inline void write (char c) { putchar (c); } inline void write (char s[]) { int pos = 0 ; while (s[pos] != '\0' ) putchar (s[pos ++]); } template <typename T> inline IOManager operator < (T x) { write (x); return *this ; } } io;struct Solver {private : static const int N = 1010 ; int n, a[N]; void input () { io > n; } void process () { int k; io > k; for (int i = 1 ; i <= k; ++ i) io > a[i], a[i] %= 9 ; int ans = 9 ; for (int i = 1 ; i <= k; ++ i) { int mul = 1 ; for (int j = 1 ; j <= i; ++ j) (mul *= a[j]) %= 9 ; ans += mul; } io < (ans - 1 ) % 9 + 1 < '\n' ; }public : void solve () { input (); while (n --) process (); } } solver;int main () { solver.solve (); return 0 ; }