Cod sursa(job #164213)

Utilizator FlorinC1996Florin C FlorinC1996 Data 23 martie 2008 18:07:17
Problema Suma divizorilor Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>   
using namespace std;   
  
const char iname[] = "sumdiv.in";   
const char oname[] = "sumdiv.out";   
  
  
  
int putere(int q, int exp)   
{   
    int V;   
  
    if (!exp)   
        return 1;   
    V = putere(q, exp / 2);   
    V = (V * V) % 9901;   
    if (exp & 1)   
        V = (V * q) % 9901;   
    return V;   
}   
  
int progresie(int q, int exp)   
{   
    int V;   
  
    if (q == 1)   
        V = (exp + 1) % 9901;   
    else if (exp == 1)   
        V = (1 + q) % 9901;   
    else if (exp == 0)   
        V = 1;   
    else if (exp & 1) {   
        V = progresie(q, exp - 1);   
        V = (1 + ((q % 9901) * V) % 9901) % 9901;   
    } else {   
        V = progresie(q, exp / 2);   
        V = (V + (putere(q, exp / 2) * (V + 9900)) % 9901) % 9901;   
    }   
    return V;   
}   
  
int main(void)   
{   
    freopen(iname, "r", stdin);   
    freopen(oname, "w", stdout);   
    int A, B;   
    int S;   
    int d;   
    int p;   
  
    scanf("%d %d", &A, &B);   
  
    S = 0;   
    for (p = 0; !(A & 1); ++p, A >>= 1)   
        ;   
    S = progresie(2, p * B);   
  
    for (d = 3; d * d <= A; d += 2) {   
        if (!(A % d)) {   
            for (p = 0; !(A % d); ++p, A /= d)   
                ;   
            S = (S * progresie(d % 9901, p * B)) % 9901;   
        }   
    }   
    if (A > 1)   
        S = (S * progresie(A % 9901, B)) % 9901;   
  
    printf("%d\n", S);   
       
    return 0;   
}