Cod sursa(job #2701462)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 31 ianuarie 2021 13:36:53
Problema Suma si numarul divizorilor Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include<bits/stdc++.h>

using namespace std;

vector<long long> prime;
vector<bool> prim(1000001);

ifstream fin("ssnd.in");
ofstream fout("ssnd.out");

#define MOD 9973

void ciur()
{
    for(long long i=2;i*i<=1000000;i++)
    {
        if(!prim[i])
        {
            for(long long j=i*i;j<=1000000;j+=i)
            {
                prim[j] = true;
            }
        }
    }

    for(long long i=2;i<=1000000;i++)
    {
        if(!prim[i])
            prime.push_back(i);
    }
}

long long power(long long a,long long n)
{
    long long res = 1;
    while(n)
    {
        if(n%2)
        {
            res = ((res % MOD) * (a % MOD)) % MOD;
        }
        a = ((a % MOD) * (a % MOD)) % MOD;
        n /= 2;
    }
    return res;
}

void calc(long long n)
{
    long long k = 0;

    long long divizori = 1;
    long long suma = 1;

    while(n > 1)
    {
        long long d = prime[k];
        long long p1 =  1;
        long long p2 = d;
        while(n % d == 0)
        {
            n /= d;
            p1 = (p1 + 1 ) % MOD;
            p2 = ((p2%MOD) * (d%MOD));
        }

        divizori =((divizori) % MOD * (p1 % MOD)) % MOD;

        long long numarator = ((p2 - 1 ) % MOD + MOD ) % MOD;
        long long numitor = power(d-1,MOD-2);
        long long fractie = ((numarator % MOD) * (numitor % MOD) ) % MOD;
        suma = ((suma % MOD) * (fractie % MOD )) % MOD;

        k++;
    }

    fout<<divizori<<" "<<suma<<'\n';
}

int main()
{
    ciur();
    long long t,n;
    fin>>t;
    while(t--)
    {
        fin>>n;
        calc(n);
        //cout<<power(n,3);
    }
    return 0;
}