Перейти к содержанию

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