#include<cmath>
#include<cstdio>
#include<bitset>
#define ll long long
#define ri register int
using namespace std;
template<typename TP>inline void read(TP&x)
{
    x=0;int f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    x*=f;
}
template<typename TP>inline void print(TP x)
{
    if(x<0)x=-x,putchar('-');
    if(x>=10)print(x/10);
    putchar(x%10+'0');
}
ll prime[66666],size;
bitset<66666>flag;
inline void make_prime(ll x)
{
    for(int i=2;i<=x;++i)
    {
        if(!flag[i]) prime[++size]=i;
        for(int j=1;j<=size&&prime[j]*i<=x;++j)
        {
            flag[prime[j]*i]=1;
            if(!(i%prime[j]))break;
        }
    }
}
ll st[66666][2],cnt;
inline void devide(ll x)
{
	for(ri i=1;i<=size;++i)
		if(x%prime[i]==0)
		{
			st[++cnt][0]=prime[i];
			while(x%prime[i]==0)
				++st[cnt][1],x/=prime[i];
		}
	if(x!=1) st[++cnt][0]=x,++st[cnt][1];
}
inline ll Pow(ll x,ll y,ll mod)
{
    ll ans=1;
    for(ll i=y;i;i>>=1)
    {
        if(i&1)ans=ans*x%mod;
        x=x*x%mod;
    }
    return ans%mod;
}
ll ans=1;
ll a,b;
inline void get_ans()
{
	for(ri i=1;i<=cnt;++i)
	{
	 	if((st[i][0]-1)%9901)
			ans=ans*(Pow(st[i][0],st[i][1]*b+1,9901)-1)*Pow(st[i][0]-1,9899,9901)%9901;
		else ans=ans*(st[i][1]+1)%9901;
	}
}
int main()
{ 
	read(a),read(b);
	make_prime(sqrt(a)+1);
	devide(a);
	get_ans();
	print(ans);
	return 0;
}

• Re:各位大佬，我这个已经改到绝望都不知道哪里错了qwq，求助 (1658) cunlidaniang 2020-04-21 22:34:11