10.18_T1 春思

题目

解题思路：

等比数列 & 乘法逆元

Accepted code：

#include<cmath>
#include<cstdio>
#include<iostream>
#define YMW 9901

using namespace std;
typedef long long ll;

ll a,b,ans=1;
ll ksm(ll x,ll y){
    ll ans=1; x%=(YMW);
    while (y){
        if (y&1) ans=ans*x%(YMW);
        x=x*x%(YMW); y>>=1;
    }
    return ans;
}
ll answer(ll x,ll y){
    if ((x-1)%(YMW)==0) return (y+1)%(YMW);
    int a=(ksm(x,y+1)+9900)%(YMW);
    int b=ksm(x-1,9899);
	return a*b%(YMW);
}
void read(ll &f) {
	f=0; char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) f=(f<<1)+(f<<3)+c-48,c=getchar();
	return;
}
int main(){
	read(a); read(b);
    int N=sqrt(a);
    for (ll i=2;i<=N;i++)
    if (a%i==0){
        ll sum=0;
        while (a%i==0) sum++,a/=i;
        ans=ans*answer(i,sum*b)%(YMW);
    }
    if (a>1) ans=ans*answer(a,b)%(YMW);
    printf("%lld",ans%(YMW));
    return 0;
}