Cod sursa(job #2188673)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 27 martie 2018 12:34:12
Problema Suma si numarul divizorilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#define M 9973
#define N 1000005

using namespace std;

bool a[N];
int sir[N];
int k=0;

void ciur()
{
    for (int i=2; i<N; i++)
        {
            if (!a[i])
            {
                sir[++k]=i;
                for (int j=2*i; j<N; j+=i)
                    a[j]=1;
            }
        }
}

void euclid(long long a, long long b, long long &x, long long &y)
{
    if (!b)
    {
        x=1;
        y=0;
        return;
    }
    euclid(b, a%b, x, y);
    long long aux;
    aux=y;
    y=x-(a/b)*y;
    x=aux;
}

int main()
{
    ifstream fin("ssnd.in");
    ofstream fout("ssnd.out");
    long long n, s, p, pr, x, y;
    int t, nr;
    ciur();
    fin >> t;
    for (int i=1; i<=t; i++)
    {
        fin >> n;
        s=1;
        p=1;
        for (int j=1; j<=k && sir[j]*sir[j]<=n; j++)
        {
            nr=0;
            pr=1;
            while(n%sir[j]==0)
                nr++,n/=sir[j],pr*=sir[j];
            pr*=sir[j];
            pr--;
            if (nr)
            {
                s=s*(nr+1);
                p=((p%M)*(pr%M))%M;
                euclid(sir[j]-1, M, x, y);
                while(x<0)
                    x+=M;
                p=((p%M)*(x%M))%M;
            }
        }
        if (n>1)
        {
            s=s*2;
            p=(p*(n+1)%M)%M;
        }
        fout << s << " " << p << "\n";
    }
    return 0;
}