Cod sursa(job #2496517)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 20 noiembrie 2019 22:52:48
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <bitset>
#define R 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
int n,t,i,j,x,factor,exp,nrdiv,prime[100000];
long long putere,sumdiv;
bitset <1000100> b;
void ciur(){
    for(i=2;i<=1000000;i++)
        if(b[i]==0){
            prime[++prime[0]]=i;
            for(j=i+i;j<=1000000;j+=i)
                b[j]=1;
        }
}
int explog(int a,int p){
    if(p==0)return 1;
    long long r=explog(a,p/2);
    if(p%2)return(((r*r)%R)*a)%R;
    return (r*r)%R;
}
int invmod(int x){
    if(x==1)return 1;
    return explog(x,R-2);
}
int main(){
    ciur();
     for(fin>>t;t--;){
        fin>>x;
        if(x==1){fout<<"1 1\n";continue;}
        nrdiv=sumdiv=1;
        for(i=1;i<=prime[0] && prime[i]<=x/prime[i] && x>1;i++)
            if(x%prime[i]==0){
                exp=0;factor=prime[i];putere=1;
                while(x%prime[i]==0){
                    putere*=factor;
                    exp++;
                    x/=prime[i];
                }
                putere*=factor;
                nrdiv*=(exp+1);
                sumdiv*=((putere-1)*invmod(factor-1))%R;
                sumdiv%=R;
            }
        if(x>1){
            nrdiv*=2;
            sumdiv*=((x*x-1)*invmod(x-1))%R;
            sumdiv%=R;
        }
        fout<<nrdiv<<" "<<sumdiv<<"\n";
    }
    return 0;
}