Digital Root

题目描述

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$。

代码

#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;
}