Cod sursa(job #2496509)

Utilizator Data 20 noiembrie 2019 22:37:48 Suma si numarul divizorilor 0 cpp-64 done Arhiva educationala 1.84 kb
``````#include <fstream>
#include <bitset>
#define R 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
int n,t,i,j,prime[100000],inv[100000],factori[1000],x,exp[1000],st,dr,mid;
bitset <1000100> b;
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 nrdiv(){
int r=1;
for(int i=1;i<=factori[0];i++)
r*=exp[i]+1;
return r;
}
int sumdiv(){
long long s=1,putere=1;
for(int i=1;i<=factori[0];i++){
putere=1;
for(int e=exp[i];e>=0;e--)
putere*=prime[factori[i]];
s=(s*(putere-1)*inv[factori[i]])%R;
}
return s;
}
int main(){
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;
}
for(i=1;i<=prime[0];i++)
inv[i]=invmod(prime[i]-1);
for(fin>>t;t--;){
fin>>x;
if(x==1){fout<<"1 1\n";continue;}
factori[0]=0;
for(i=1;i<=prime[0] && prime[i]<=x/prime[i] && x>1;i++)
if(x%prime[i]==0){
factori[++factori[0]]=i;
exp[factori[0]]=0;
while(x%prime[i]==0) {
x/=prime[i];
exp[factori[0]]++;
}
}
if(x>1){
st=1;dr=prime[0];
while(st<dr){
mid=(st+dr)/2;
if(prime[mid]==x){
factori[++factori[0]]=mid;
exp[factori[0]]=1;
}
if(prime[mid]<x)st=mid+1;
else dr=mid-1;
}
}
fout<<nrdiv()<<" "<<sumdiv()<<"\n";
}
return 0;
}
``````