Cod sursa(job #1418697)

Utilizator crisovidiuCristian Ovi crisovidiu Data 13 aprilie 2015 18:57:53
Problema Suma si numarul divizorilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
//#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <limits>
#include <fstream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
using namespace std;
ifstream cin("ssnd.in");
ofstream cout("ssnd.out");

#define nmax 1000010
#define mod 9973
#define mp make_pair
#define pb push_back
#define int64 long long
#define pii pair<int,int>
#define inf numeric_limits<int>::max()
#define forv(v,it) for (vector<int>::iterator it=v.begin();it!=v.end();it++)

int64 x;
int n,k,nrDiv,f1,f2,prim[nmax],s;
bool ciur[nmax];

int putlg(int64 a,int64 b)
{
    int64 i,sol;
    sol=1;
    for (i=0;(1<<i)<=b;i++)
    {
        if ((1<<i)&b) sol=(sol*a)%mod;
        a=(a*a)%mod;
    }
    return sol;
}

int main()
{
    int64 i,j;
    prim[++prim[0]]=2;
    for (i=4;i<=nmax-10;i+=2) ciur[i]=1;
    for (i=3;i<=nmax-10;i+=2)
        if (!ciur[i])
        {
            prim[++prim[0]]=i;
            for (j=i*i;j<=nmax-10;j+=2*i) ciur[j]=1;
        }
    for (cin>>n;n;n--)
    {
        cin>>x;
        s=nrDiv=1;
        for (i=1;i<=prim[0] && x>1;i++)
            if (x%prim[i]==0)
            {
                k=0;
                while (x%prim[i]==0)
                {
                    k++;
                    x/=prim[i];
                }
                if (k)
                {
                    nrDiv*=k+1;
                    f1=putlg(prim[i],k+1);
                    f2=putlg(prim[i]-1,mod-2);
                    f1--;if (f1<0) f1+=mod;
                    s=(((s*f1)%mod)*f2)%mod;
                }
            }
        if (x>1) cout<<2<<" "<<x+2<<'\n';
        else cout<<nrDiv<<" "<<s<<'\n';
    }
}