class="markdown_views prism-atom-one-light">

原理：

若a，b互质，则有a的逆元，等于a%b的逆元;
所以可以在把大整数转为数字时取模。然后再求逆元

例题

P2613 【模板】有理数取余 题目描述 给出一个有理数c = a/b，求c mod19260817的值。
输入输出格式
输入格式： 一共两行。 第一行，一个整数a。
第二行，一个整数b。 输出格式： 一个整数，代表求余后的结果。如果无解，输出Angry! 输入输出样例
输入样例#1： 复制 233
666 输出样例#1： 复制 18595654 说明 对于所有数据，0<=a，b<=10^100001.

code

#include using namespace std; const int N = 1e5 + 7; #define mo 19260817 void exgcd(int a,int b,int &d,int &x,int &y) { if(!b){d = a;x = 1;y = 0;return ;} exgcd(b,a%b,d,y,x);y -= x*(a/b); } int A,B; char sa[N],sb[N]; int main() { cin>>sa>>sb;int lena = strlen(sa),lenb = strlen(sb); for (int i = 0;i < lena;i++) A = (A*10 + sa[i] - '0')%mo; for (int i = 0;i < lenb;i++) B = (B*10 + sb[i] - '0')%mo; int x,y,d;exgcd(B,mo,d,x,y); if(d != 1){puts("Angry!");return 0;} x = (x + mo)%mo;printf("%lld",(long long)A*x%mo);return 0; }