ACM SGU/volume 1/118

118. Digital Root

Условие

Пусть функция $s(n)\!$ равна сумме цифр числа $n\!$. Тогда функция $f(x)\!$ равна $s(x)\!$, если $s(x)<10\!$, и равна $f(s(x))\!$, если $s(x)\geq 10\!$. Необходимо вычислить значение выражения $f(A_{1}\cdot A_{2}\cdot \ldots \cdot A_{N}+A_{1}\cdot A_{2}\cdot \ldots \cdot A_{N-1}+\ldots +A_{1}\cdot A_{2}+A_{1})\!$.

Ограничения

$N\leq 1000\!$

Идея решения

Если повычислять значения $f(x)\!$ для разных $x\!$, то несложно заметить:

f(x) = (x % 9 == 0 ? 9 : x % 9)

Значит значение выражения из условия мы можем вычислить за $O(n^{2})\!$ в лоб. А можем и за $O(n)\!$, если применить схему Горнера (вынести за скобку $A_{1}\!$, потом $A_{2}\!$ и так далее).

Реализация на C++

#include <cstdio>
using namespace std;

#define forn(i, n) for (i = 0; i < (n); ++ i)
#define forab(i, a, b) for (i = (a); i <= (b); ++ i)
#define forv(it, v) for (it = (v).begin (); it != (v).end (); ++ it)

int A[10000] = {0};

int main ()
{
	int k;
	scanf ("%d", &k);
	int ik;
	forn (ik, k)
	{
		int i, j;
		int n;
		scanf ("%d", &n);
		forn (i, n)
		{
			scanf ("%d", &A[i]);
			A[i] %= 9;
		}
		
		int s = 1;
		for (i = n - 1; i > 0; -- i)
			s = (1 + A[i] * s) % 9;
		s = (s * A[0]) % 9;
		if (s == 0) s = 9;
		printf ("%d\n", s);
	}	
	
	return 0;
}