Просмотр кода страницы ACM SGU/volume 1/118

=118. Digital Root=

== Условие ==
Пусть функция <math>s(n)\!</math> равна сумме цифр числа <math>n\!</math>. Тогда функция <math>f(x)\!</math> равна <math>s(x)\!</math>, если <math>s(x) < 10\!</math>, и равна <math>f(s(x))\!</math>, если <math>s(x) \ge 10\!</math>.
Необходимо вычислить значение выражения <math>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)\!</math>.

== Ограничения ==
<math>N \le 1000\!</math>

== Идея решения ==
Если повычислять значения <math>f(x)\!</math> для разных <math>x\!</math>, то несложно заметить: <syntaxhighlight lang="cpp">f(x) = (x % 9 == 0 ? 9 : x % 9)</syntaxhighlight> Значит значение выражения из условия мы можем вычислить за <math>O(n^2)\!</math> в лоб. А можем и за <math>O(n)\!</math>, если применить схему Горнера (вынести за скобку <math>A_1\!</math>, потом <math>A_2\!</math> и так далее).

== Реализация на C++ ==
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>
[[Категория:ACM SGU|volume 1/118]]