Cod sursa(job #931154)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 28 martie 2013 00:15:46
Problema Suma divizorilor Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>

using namespace std;

#define MOD 9901

long long N, M;

ifstream f("sumdiv.in");
ofstream g("sumdiv.out");

long long pow( long long a, long long p ){
 
    long long res = 1;
 
    for ( long long j = 0; ( 1 << j ) <= p; ++j ){
 
        if ( ( 1 << j ) & p )
            res = ( res * a ) % MOD;
 
        a = ( a * a ) % MOD;
    }
 
    return res;
}

void sol()
{
	f >> N;
	f >> M;

	long long sd = 1, v = 0;

	for(long long d = 2; d * d <= N && N > 1; ++d)
	{
		if(N % d) continue;
		v = 0;

		while(N % d == 0)
		{
			N /= d;
			++v;
		}
		
		if(d % MOD == 1)
			sd *= 1LL * (v + 1) % MOD;
		else
		{
			long long p1 = ( pow ( d, v * M + 1 ) + MOD - 1 ) % MOD;
            long long p2 = pow( d - 1, MOD - 2 ) % MOD;

			sd *= 1LL * p1 * p2;
			sd %= MOD;
		}
	}

	 if ( N > 1 ){
 
        if ( N % MOD == 1 )
            sd = ( sd * 1LL * ( M % MOD + 1 ) ) % MOD;
        else{
                long long p1 = ( pow ( N, M + 1) + MOD - 1 ) % MOD;
                long long p2 = pow ( N - 1, MOD - 2 ) % MOD;
 
                sd *= 1LL * p1 * p2;
                sd %= MOD;
        }
    }
 
     if ( N == 0 )
        g << 0 << "\n";
     else
        g << sd << "\n";
}

int main()
{
	sol();
	return 0;
}