Cod sursa(job #2774527)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 11 septembrie 2021 20:17:08
Problema Suma si numarul divizorilor Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#define N 1000001
#define M 9973
long long n;
int t,k,p[80000],i,j,w,z,r,x,y;
char v[N];
int P(int x,int p)
{
	int r=1;
	for(x%=M;p;p>>=1,x=(x*x)%M)
		if(p&1)
			r=(x*r)%M;
	return r;
}
int main()
{
	freopen("ssnd.in","r",stdin),freopen("ssnd.out","w",stdout);
	for(i=2;i<N;++i)
		if(!v[i])
			for(j=2*i;j<N;j+=i)
				v[j]=1;
    for(i=2;i<N;++i)
        if(!v[i])
            p[++k]=i;
	for(scanf("%d",&t);t;--t) {
        for(scanf("%lld",&n),w=z=i=1;i<=k&&1LL*p[i]*p[i]<=n;++i) {
            if(n%p[i])
                continue;
            for(r=0;n%p[i]==0;n/=p[i],++r);
            w*=(r+1),x=(P(p[i],r+1)-1)%M,y=P(p[i]-1,M-2)%M,z=(((z*x)%M)*y)%M;
        }
        if(n>1)
            w*=2,z=(1LL*z*(n+1)%M);
        printf("%d %d\n",w,z);
    }
    return 0;
}