给出一个有理数\( c=\frac{a}{b} \) ? ，求 \( c mod19260817 \) 的值。
输入格式：
一共两行。
第一行，一个整数 \( a \) 。
第二行，一个整数 \( b \)。
输出格式：
一个整数，代表求余后的结果。如果无解，输出Angry!
对于所有数据， \( 0\leq a,b \leq 10^{10001}0≤a,b≤1010001 \)
很平常的一道膜板题，求解除法取模需要利用乘法逆元的知识
直接扩展欧几里得算法求解逆元
至于数据范围，可以直接在读入时取模，不需要毒瘤高精度qwq
下面放代码
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; long long a,b; const int MOD = 19260817; long long read(void){ long long x=0; char c; c=getchar(); while(c==‘ ‘||c==‘\n‘||c==‘\r‘||c==‘\0‘) c=getchar(); while(c<=‘9‘&&c>=‘0‘){ x=((x*10%MOD)+(c-‘0‘)%MOD)%MOD; c=getchar(); } return x; } long long exgcd(long long a,long long b,long long &x,long long &y){ if(b==0){ x=1; y=0; return a; } long long res = exgcd(b,a%b,x,y); long long t=x; x=y; y=t-a/b*y; return res; } int main(){ a=read(); // printf("%d\n",a); b=read(); // printf("%d\n",b); long long x,y; if(exgcd(b,MOD,x,y)==1){ long long nx=((x%MOD)+MOD)%MOD; printf("%lld",((a%MOD)*(nx%MOD))%MOD); } else{ printf("Angry!\n"); } return 0; }
原文：https://www.cnblogs.com/dreagonm/p/9364518.html