P2613 【模板】有理数取余

P2613 【模板】有理数取余

有理数取余,你亲爱的奥赛教练教过你么?(好像没有)

逆元? 肯定是有的吧

然后这个题就可以使用逆元避免尴尬的分数取余了

不过输入有些鬼畜。

判断无解时就判断一下分母是否为零就行了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
const long long mod=19260817;
long long read()
{
	long long res=0;
	char c=getchar();
	while(c>'9'||c<'0')	
		c=getchar();
	while(c>='0'&&c<='9')
	{
		res=(res*10+c-'0')%mod;
		c=getchar();
	}
	return res;
}
long long kasumi(long long base,int pow)
{
	long long res=1;
	while(pow)
	{
		if(pow&1)
			res=(res*base)%mod;
		base=(base*base)%mod;
		pow>>=1;
	}
	return res;
}
int main()
{
	long long a=read(),b=read();
	if(b==0)
	{
		printf("Angry!");
		return 0;
	}
	printf("%lld",(a*kasumi(b,mod-2))%mod);
}
原文地址:https://www.cnblogs.com/Lance1ot/p/9371840.html