Cod sursa(job #2767277)

Utilizator ps2001Silviu Popescu ps2001 Data 5 august 2021 14:51:17
Problema Suma divizorilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

int exp(int a, int b) {
    if (b == 0) return 1;
    if (b % 2 == 0) return exp(a*a, b / 2);
    return a*exp(a*a, b/2);
}

int main()
{
    ifstream fin("sumdiv.in");
    ofstream fout("sumdiv.out");

    int a, b;
    fin >> a >> b;

    vector<int> prime;
    vector<bool> prim(100001, true);

    for (int i = 2; i <= 100000; i++) {
        if (prim[i] == true) {
            prime.push_back(i);
            for (int j = i * 2; j <= 100000; j += i)
                prim[j] = false;
        }
    }

    long long number = 1, sum = 1, d = 0;

    //cout << prime[5] << '\n';

    while (a > 1 && prime[d] * prime[d] <= a) {
        long long p = 1, ok = 0;

        while (a % prime[d] == 0) {
            p *= prime[d];
            a /= prime[d];
            ok = 1;
        }

        int copy = b;
        if (ok == 1) {
            p = exp(prime[d], copy);
            //cout << p << '\n';
            //p /= prime[d];
            sum *= (p * prime[d] - 1) / (prime[d] - 1) % 9901;
            //cout << sum << '\n';
        }

        d++;
    }

    if (a != 1) {

        int copy = b;
        long long p = 1;

        p = exp(a, copy);
        sum *= ((p * a) - 1) / (a - 1) % 9901;
    }

    fout << sum << '\n';

    return 0;
}