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