这个题比较离谱的地方是,a和b都和模数不互质。
但是我们很容易发现,\(a,b,p^k\) 有且仅有公因子\(p\)
利用这个结论,我们可以记录a和b中包含的\(p\)的个数单独进行计算,最后合并答案。
如果模数是\(p^x\),\(p\)是质数,我们可以使用欧拉定理得到逆元即为\(a^{p^{x-1}-1}\),当然也可以用exgcd
代码如下:
#include<iostream>//注意模数不互质就行
#include<cstdio>//
#include<cstring>//
#include<algorithm>
#define int unsigned long long
using namespace std;
int x,y;
inline int r()
{
int s=0,k=1;char c=getchar();
while(!isdigit(c))
{
if(c=='-')k=-1;
c=getchar();
}
while(isdigit(c))
{
s=s*10+c-'0';
c=getchar();
}
return s*k;
}
int exgcd(int a,int b)
{
if(!b)
{
x=1;
y=0;
return a;
}
int g=exgcd(b,a%b);
int xx=x;
x=y;
y=xx-y*(a/b);
return g;
}
int n,k,p,a,b,up,down,pa,pb,t,ta,tb;
int ny(int t,int md)
{
exgcd(t,md);
return ((x%md)+md)%md;
}
int quick_pow(int f,int tot,int mod)
{
if(tot==0)return 1;
int base=f;
int ans=1;
while(tot)
{
if(tot&1)
{
ans*=base;
ans%=mod;
}
base*=base;
base%=mod;
tot>>=1;
}
return ans;
}
signed main()
{
cin>>n>>k>>p;t=1;
for(int i=1;i<=k;i++)t=t*p;
if(!k)p=1;
int sb=t/p;
ta=tb=1;
int ans=1;
for(int i=1;i<=n;i++)
{
a=r();b=r();
while(a%p==0)
{
pa++;
a=a/p;
}
while(b%p==0)
{
pb++;
b=b/p;
}
ans*=a%t*quick_pow(b,t-sb-1,t)%t;
ans%=t;
printf("%llu\n",((quick_pow(p,pa-pb,t)%t)*ans)%t);
}
}
``