C++ P2613 【模板】有理数取余

题目描述

给出一个有理数 $c=frac{a}{b}$ ，求 $c mod 19260817$ 的值。

输入输出格式

输入格式：

一共两行。

第一行，一个整数a。
第二行，一个整数b。

输出格式：

一个整数，代表求余后的结果。如果无解，输出Angry!

输入输出样例

输入样例#1：

233
666

输出样例#1：

18595654

说明

对于所有数据， $0leq a,b leq 10^{10001}$

个人思路：

一开始还以为直接a/b就行了，后来发现范围太大了（而且 $frac{aoldsymbol{mod}P}{boldsymbol{mod}P} eq frac{a}{b}oldsymbol{mod}P$ ）
看了一下题解，思路是用费马小定理（ $a^{P-1}equiv 1(oldsymbol{mod }P)$ ）求逆元即可（因为p刚好是质数）
也就是说，因为a*b=1，所以 $a*b=a^{P-1} ightarrow a^{P-2}=b$
在获取数字的过程中，为了避开使用高精度，一位一位地读，每读完一位就%一次P即可保证数字不超范围（取模的基本性质）
因为我们利用了取模的基本性质，所以最终答案当然不能直接a/b,所以我们需要用快速幂求b，也就是计算 $a^{P-2}$ ，也就计算出了b的值
之后，a与b相乘并模P即可

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
int p=19260817;
char c[10010];
int read(){
	scanf("%s",c);
	ll length=strlen(c);
	ll num=0;
	for(int i=0;i<length;i++){
		num*=10;
		num+=(c[i]-'0');
		num=num%p;
	}
	return num;
}
long poww(ll a,ll b){
	long ans=1;
	while(b){
		if(b&1){
			ans=(ans*a)%p;
		}
		a=(a*a)%p;
		b=b>>1;
	}
	return ans;
}
int main(){
	ll a,b;
	a=read(),b=read();
	if(b==0){
		cout<<"Angry!"<<endl;
		return 0;
	} 
	cout<<a*poww(b,p-2)%p<<endl;
	return 0;
}