# Cod sursa(job #2495939)

Utilizator Data 19 noiembrie 2019 23:57:14 Suma si numarul divizorilor 100 cpp-64 done Arhiva educationala 1.76 kb
``````#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
int cont,t,s,prim[1000010],nrprim=1;
long long n;
bitset<1000010>ciur;
int putere(int a, int b) {
int r = 1;
a%=9973;
while (b!=0) {
if (b%2==1){
r = (r*a)%9973;
}
a = a*a%9973;
b=b/2;

}

return r;

}

int main(){
prim[nrprim]=2;
for (int i=3;i<=1000000;i+=2) {
if (ciur[i]==0){
nrprim++;
prim[nrprim] =i;
for (int j=i+i;j<=1000000;j+=i){
ciur[j]=1;
}

}

}
fin>>t;
for(int i=1;i<=t;i++){
fin>>n;
cont=1;
s=1;
for(int i=1;n!=1 && 1LL*prim[i]*prim[i]<=n;i++){
if(n%prim[i]==0){
int power=0;
int pr=prim[i];

while(n%pr==0 ){

power++;
n=n/pr;

}

long long exp=putere(pr,power+1);
exp--;
if(exp<0){
exp+=9973;
}

cont*=(power+1);

int exp2=putere((pr+9972)%9973,9971);
exp=exp*exp2%9973;
s=s*exp%9973;

}

}

if(n!=1){
int pr=n%9973;
int power=1;
cont*=(power+1);

int exp=putere(pr,power+1);
exp--;
if (exp < 0){
exp+=9973;
}

int exp2=putere((pr+9972)%9973,9971);
exp=exp*exp2%9973;
s=s*exp%9973;

}

fout<<cont<<" "<<s<<"\n";

}

}

``````