# Cod sursa(job #2495954)

Utilizator Data 20 noiembrie 2019 00:37:39 Suma si numarul divizorilor 40 cpp-64 done Arhiva educationala 1.49 kb
``````#include<fstream>
#include<bitset>
#define MOD 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
long long n, m;
int T,rest,nr,a,b,p;
bitset<1000010> v;
int prime[1000010];
int divizori[1000010];
int puteri[1000010];

int putere(int a,int b) {
int r=1;
while(b){
if(b%2==1)
r=(r*a)%MOD;
a=a*a%MOD;
b/=2;
}
return r;
}

int main(){
fin>>T;
///ciur
for(int i=2;i<=1000000;i++){
if(v[i]==0){
prime[++p]=i;
for(int j=i+i;j<=1000000;j+=i)
v[j]=1;
}
}
///
for(int t=1;t<=T;t++){
fin>>n;m=n;
p=0;

for(int i=1;prime[i]*prime[i]<=n;i++){

if(m%prime[i]==0){
p++;
divizori[p]=prime[i];
puteri[p]=0;

while(m!=1 && m%prime[i]==0){
puteri[p]++;
m/=prime[i];
}

}
}
if(m!=1){
divizori[++p]=m%MOD;
puteri[p]=1;
}
nr=1;rest=1;
for(int i=1;i<=p;i++) {
nr=nr*(1+puteri[i]);

a=putere(divizori[i],puteri[i]+1);
a--;
if(a<0)
a+=MOD;
b=putere( (divizori[i]+MOD-1)%MOD , MOD-2);

a=a*b%MOD;

rest=rest*a%MOD;
}
fout<<nr<<" "<<rest<<"\n";
}

return 0;
}

``````