Cod sursa(job #3375595)

Utilizator popescu_georgePopescu George popescu_george Data 12 noiembrie 2026 16:17:35
Problema Suma divizorilor Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 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;
	if(cin>>a>>b,a<2)
		return cout<<-1,0;
	int c=b%(N-1),d=1;
	if(cin>>a>>b,c=b%(N-1),!(a&1)) {
		int p=1;
		for(a>>=1;!(a&1);a>>=1,++p);
		if(d=A(2,(c*p+1)%(N-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)%(N-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?p-1:N-1,N-2)%N;
		} else
			d=d*(b%N+1)%N;
	}
	return cout<<d,0;
}