Cod sursa(job #3287815)

Utilizator tudorhTudor Horobeanu tudorh Data 19 martie 2025 14:51:06
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
#define int128 __int128
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
bool prime[1000001];
vector<int> divi;
void eratostene()
{
    for(int i=2;i<=1000000;i++)
    {
        if(!prime[i])
        {
            divi.push_back(i);
            for(int j=i;1ll*i*j<=1000000;j++)
                prime[i*j]=1;
        }
    }
}
int mod=1e9+7;
long long power(long long base,int128 power)
{
    long long res=1;
    while(power)
    {
        if(power%2)
        {
            res*=base;
            res%=mod;
        }
        base*=base;
        base%=mod;
        power/=2;
    }
    return res;
}
long long invers(int n)
{
    return power(n,mod-2);
}
int main()
{
    int tc;
    fin>>tc;
    while(tc--)
    {
    long long a,b;
    long long s=1;
    fin>>a;
    b=1;
    long long nr=1;
    eratostene();
    int pos=0;
    int128 unu=1;
    while(pos<divi.size() && divi[pos]*divi[pos]<=a)
    {
        int exp=0;
        while(a%divi[pos]==0)
        {
            a/=divi[pos];
            exp++;
        }
        nr*=(exp+1);
        if(exp)
        {
            int128 exp2=unu*exp*b+1;
            s=s*((power(divi[pos],exp2)-1+mod)%mod)%mod*invers(divi[pos]-1)%mod;
        }
        pos++;
    }
    if(a!=1)
    {
        s=s*((power(a,b+1)-1+mod)%mod)%mod*invers(a-1)%mod;
        nr*=2;
    }
    fout<<nr<<' '<<s<<'\n';
    }
    return 0;
}