洛谷P2613 【模板】有理数取余

题目背景

原题链接点击这里

第一眼看，题意很明确，思路就是求b的逆元，
（不会逆元的，可以看我这一篇博客
但是一看数据范围\(10^{10001}\)
一开始还在想也不要打高精，仔细想想不用
因为模运算具有加减乘性质，加减乘中间任何数取模都不会影响模的结果
所以我们把一个数用字符串读入，然后\(x=(x*10+s[i]-'0')%p\)
对a取模得到的结果不影响，至于为什么对b取模得到的结果也不影响
还是去看我那篇博客里面有讲
然后就是递归求单个逆元

代码实现

#include
using namespace std;
typedef long long ll;

ll p,ans,t,a,b;
ll getinv(int x){
	return x==1?1:1ll*(p-(p/x))*getinv(p%x)%p;
}
ll exch(string s){
	ll x=0;
	int len=s.size();
	for(int i=0;i>sa>>sb;
	a=exch(sa);
	b=exch(sb);
	ans=a*getinv(b)%p ;
	cout<