Pagini recente » Cod sursa (job #2090695) | Cod sursa (job #528430) | Arhiva de probleme | Cod sursa (job #122999) | Cod sursa (job #2495245)
#include <fstream>
#include <bitset>
#define mod 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
long long n;
int t,i,j,p[1000010],m,sum,nr,cnt,x,y,d;
bitset <1000010> f;
int pow(int a, int b) {
int r = 1;
a%=mod;
while(b) {
if(b&1)
r=(r*a)%mod;
a=a*a%mod;
b>>=1;
}
return r;
}
int main() {
p[m=1]=2;
for(i=3;i<=1000000;i+=2){
if(!f[i]){
p[++m]=i;
for(j=3*i;j<=1000000;j+=2*i)
f[j]=1;
}
}
fin>>t;
for(;t--;){
fin>>n;
nr=1; sum=1;
for(i=1;n!=1 && p[i]<=n/p[i];i++){
if(n%p[i]==0){
d=p[i]; cnt=1;
while(n%d==0){
cnt++;
n/=d;
}
nr*=cnt;
x=pow(d,cnt);
x--;
if(x<0)
x+=mod;
y=pow((d+mod-1)%mod,mod-2);
x=x*y%mod;
sum=sum*x%mod;
}
}
if(n!=1){
d=n%mod;
cnt=2;
nr=nr*cnt;
x=pow(d,cnt);
x--;
if(x<0)
x+=mod;
y=pow((d+mod-1)%mod,mod-2);
x=x*y%mod;
sum=sum*x%mod;
}
fout<<nr<<" "<<sum<<"\n";
}
return 0;
}