Cod sursa(job #3375569)

Utilizator popescu_georgePopescu George popescu_george Data 12 noiembrie 2026 14:40:17
Problema Suma divizorilor Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<fstream>
using namespace std;
ifstream cin("sumdiv.in");
ofstream cout("sumdiv.out");
const int N=9901;
int A(int a,int n)
{
	int b=1;
	for(;n;a=a*a%N,n>>=1)
		if(n&1)
			b=a*b%N;
	return b;
}
int main()
{
	int a,b,c,d=1;
	if(cin>>a>>b,c=b%(N-1),a&&!(a&1)) {
		int p=1;
		for(a>>=1;!(a&1);a>>=1,++p);
		if(d=A(2,c*p+1)-1,d<0)
			d+=N;
	}
	for(int i=3;i*i<=a;i+=2)
		if(a%i<1) {
			int p=1,q;
			for(a/=i;a%i<1;a/=i,++p);
			if(q=A(i,c*p+1)-1,q<0)
				q+=N;
			d=d*q%N*A(i-1,N-2)%N;
		}
	if(a>1) {
		int p=a%N;
		if(p!=1) {
			int q=A(p,c+1)-1;
			if(q<0)
				q+=N;
			d=d*q%N*A(p-1,N-2)%N;
		} else
			d=d*(b%N+1)%N;
	}
	return cout<<(a?d:0),0;
}