Длинные числа

[dimon_snake]

Здравствуйте, нужна ваша помощь.
Есть выражение типа 1^n+2^n+3^n+4^n. Нужно посчитать кол-во нулей в конце этого числа. При этом 0<=n<=1000.
Здесь обязательно использовать длинные числа, или кол-во нулей в конце можно узнать и без них? Ведь 2^1000 это уже около 300 символов, а там еще 3 и 4. Заранее спасибо.

[Аватар]

Здесь показано, что только для n=1, 2 и 3 делится на 5, что равносильно тому, что заканчивается на 0 (поскольку четная сумма). Надо полагать 1 ноль для n=1 и 2. И два нуля для n=3 --> длиной арифметики не надо. Но попробуй )

[Dekay]

о! Красота
На самом деле все ооочень просто

1+3^n+2^n(2^n+1) = const*10^k = const*2^k*5^k
Давай посчитаем двойки.
И тут все зависит от 3^n+1 ради прикола выпишем первые пять значений и посчитаем там количество двоек. Их, как оказывается, или 1 или 2. И значения чередуются.
Значит ответ или 1 или 2 илил 0.
Разбираемся с пятерками. Можно снова что-нить найти, но зачем? Если можно просто насчитать эту сумму по модулю 100, 10, 1? Вот и все.

Длинка, для проверки
И само решение

int pow(int a, int p, int mod) {
    if (p == 0) return 1;
    if (p%2 == 0) return pow(a*a%mod, p/2, mod);
    else return a*pow(a, p-1, mod)%mod;
}

bool ch(int n, int k) {
    return ((1+pow(2, n, k)+pow(3, n, k)+pow(4, n, k))%k == 0);
}

int main() {
    // freopen("input.txt", "r", stdin);
    forn(n, 1001) {
        int k = 10000;
        bool f = false;
        for(int i = 5; i >= 0; i--, k/=10){
            if (ch(n, k)) {
                cout << i-1 << " ";
                f = true;
                break;
            }
        }
        if (!f)
        cout << 0 << " ";
    }
    return 0;
}

Нужно больше задач! Боооольше!

[Plague]

var n, a:integer;
begin
  readln(n);
  if n mod 20 = 5 then a:=1 else a:=0;
  n:=n mod 4;
  writeln(n div 2 mod 2 + n mod 2 + a);
end.