Cod sursa(job #2306518)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 decembrie 2018 14:57:27
Problema Suma si numarul divizorilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
using namespace std;
const int N=1000001,M=9973;
long long n;
int t,k,p[N],i,j,w,z,r,x,y;
bool 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()
{
	ifstream f("ssnd.in");
	ofstream g("ssnd.out");
	for(i=1;((i*i)<<1)+(i<<1)<N;i++)
		if(!(v[i>>3]&(1<<(i&7))))
   			for(j=((i*i)<<1)+(i<<1);(j<<1)+1<N;j+=(i<<1)+1)
        		v[j>>3]|=(1<<(j&7));
	for(p[++k]=2,i=1;2*i+1<N;i++)
		if(!(v[i>>3]&(1<<(i&7))))
   			p[++k]=2*i+1;
	for(f>>t;t;t--)
    {
        for(f>>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);
        g<<w<<" "<<z<<"\n";
    }
}