Cod sursa(job #1108311)

Utilizator addy01adrian dumitrache addy01 Data 15 februarie 2014 16:13:45
Problema Suma si numarul divizorilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#define mod 9973
#define maxn 1000000
#include <cstring>
using namespace std;
ifstream in("ssnd.in");
ofstream out("ssnd.out");
bool c[maxn];
int prime[maxn];
void ciur()
{
    int i,j;
    c[0]=1;
    c[1]=1;
    for(i=4;i<=maxn;i+=2)
        c[i]=1;
    for(i=3;i*i<=maxn;i+=2)
        if(c[i]==0)
            for(j=i*i;j<=maxn;j=j+2*i)
                c[j]=1;
int ct=0;
      for(i=2;i<=maxn;i++)
        if(c[i]==0)
            prime[++ct]=i;
}

int lgpow(int b,int p)
{
    if(p==0)
        return 1;
    if(p==1)
        return b;
    if(p%2==0)
        return lgpow(b*b,p/2);
    else
        return b*lgpow(b*b,(p-1)/2);
}

void solve(int x)
{
    int i,d[50],p[20],ct=0;
    memset(d,0,sizeof(d));
    int lim=x,y;
    for(y=1,i=prime[y];i<lim&&x!=1;y++)
        {
            i=prime[y];
            if(x%i==0)
        {
            ct++;
            p[ct]=i;
            while(x%i==0)
            {
                x=x/i;
                d[ct]++;
            }
        }
        }
        int nr=1,sum=1;
        for(i=1;i<=ct;i++)
            {
                nr=nr*(d[i]+1);
                sum=(sum % mod)*((lgpow(p[i],d[i]+1)-1)/(p[i]-1) % mod);
            }
            out<<nr<<" "<<sum<<"\n";
}

int main()
{
    int t,n;
    in>>t;
    ciur();
    while(t--)
    {
        in>>n;
        solve(n);
    }
    return 0;
}