Cod sursa(job #931127)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 27 martie 2013 23:54:00
Problema Suma divizorilor Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <bitset>

using namespace std;

const long long MAX_N = 50000001;
const long long MOD = 9901;

long long N, M;
long long T, K, P[MAX_N];
bitset<MAX_N> viz;

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

long long pow(long long x, long long p)
{
	long long rez = 1;
	x %= MOD;

	for(;p;p>>=1)
	{
		if(p&1)
		{
			rez *= x;
			rez %= MOD;
		}

		x *= x;
		x %= MOD;
	}
	return rez;
}

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

	long long sd = 1;

	for(long long i = 1; i<= K && 1LL * P[i] * P[i] <= N; ++i)
	{
		if(N % P[i]) continue;
		long long p = 0;

		while(N % P[i] == 0)
		{
			N /= P[i];
			++p;
		}

	

		long p1 = (pow(P[i], p+1) - 1) % MOD;
		long p2 = pow(P[i]-1, MOD-2) % MOD;

		sd = (((sd * p1) % MOD) * p2) % MOD;
	}

	 if ( M > 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();
}