Cod sursa(job #391892)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 6 februarie 2010 14:10:33
Problema Suma divizorilor Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>

using namespace std;

const int MOD = 9901;

ifstream fin ("sumdiv.in");
ofstream fout ("sumdiv.out");

int A, B, S = 1;

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

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

	return sol;
}

inline int make(int i, int p)
{
	if(i % MOD == 1)
		return p*B + 1;

	return (pow(i, 1LL*p*B+1) + MOD - 1) * (pow(i-1, MOD-2)) % MOD;
}

int main()
{
	fin >> A >> B;

	int a = A;
	for(int i = 2; i*i <= A; ++i)
	{
		int p = 0;
		while(a % i == 0)
			a /= i, ++p;

		if(p)
			S *= make(i, p),
			S %= MOD;
	}

	if(a > 1)
		S *= make(a, 1),
		S %= MOD;

	fout << S;
}