ACM SGU/volume 1/118

118. Digital RootПравить

УсловиеПравить

Пусть функция   равна сумме цифр числа  . Тогда функция   равна  , если  , и равна  , если  . Необходимо вычислить значение выражения  .

ОграниченияПравить

 

Идея решенияПравить

Если повычислять значения   для разных  , то несложно заметить:

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

Значит значение выражения из условия мы можем вычислить за   в лоб. А можем и за  , если применить схему Горнера (вынести за скобку  , потом   и так далее).

Реализация на 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;
}