Cod sursa(job #2713280)

Utilizator AlinaFloreaFlorea Alina AlinaFlorea Data 27 februarie 2021 16:28:00
Problema Suma si numarul divizorilor Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define MOD 9973
using namespace std;
ifstream f("ssnd.in");
ofstream g("ssnd.out");
int vp[100005];
int n,nrdiv,cnt,key;
long long s,x;
int prim[1000005];
void ciur(){
    prim[0]=1;
    prim[1]=1;
    for(int i=2; i<=1000000; i++)
        if(prim[i]==0){
            for(int j=2; j*i<=1000000; j++)
                prim[i*j]=1;
            vp[++cnt]=i;
        }
}
int powerLog(int a, int b){
    long long key=1;
    while(b){
        if(b%2)
            key=1LL*a*key%MOD, b--;
        a=1LL*a*a%MOD;
        b/=2;
    }
    return key;
}
int main()
{
    f>>n;
    ciur();
    /*for(int i=1; i<=cnt; i++)
        cout<<vp[i]<<" ";*/
    for(int i=1; i<=n; i++){
        f>>x;
        nrdiv=1;
        s=1;
        for(int j=1; j<=cnt && 1LL*vp[j]*vp[j]<=x; j++){
            key=0;
            if(x%vp[j]==0){
                while(x%vp[j]==0){
                    key++;
                    x/=vp[j];
                }
                nrdiv*=(key+1);
                long long sum=1LL*(powerLog(vp[j], key+1)-1)*(powerLog(vp[j]-1,MOD-2))%MOD;
                s=1LL*s*sum%MOD;
            }
        }
        if(x!=1){
            nrdiv*=2;
            long long sum=x+1;
            s=1LL*s*sum%MOD;
        }
        g<<nrdiv<<" "<<s<<'\n';
    }
    return 0;
}