题目地址：

https://www.luogu.com.cn/problem/P2613

题目描述：
给出一个有理数$c=\frac{a}{b}$，求$c\mathrm{mod}19260817$的值。
这个值被定义为$bx\equiv a(\mathrm{mod}19260817)$的解。

输入格式：
一共两行。
第一行，一个整数$a$。
第二行，一个整数$b$。

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

数据范围：
对于所有数据，保证$0\le a\le 10^{10001}$，$1\le b\le 10^{10001}$，且$a,b$不同时是$19260817$的倍数。

令$p=19260817$，可验证$p$是素数。那么即是要求$(x,y)$使得$bx+py=a$的解，并且使得$x$取最小正整数，参考https://blog.csdn.net/qq_46105170/article/details/126221151。代码如下：

#include <iostream>
using namespace std;

const int P = 19260817;
int a, b;

void fast_read(int &x) {
    
  char ch;
  while (!isdigit(ch = getchar()));
  for (; isdigit(ch); ch = getchar()) {
    
    x = x * 10 + ch - '0';
    x %= P;
  }
}

int exgcd(int a, int b, int &x, int &y) {
    
  if (!b) {
    
    x = 1, y = 0;
    return a;
  }

  int d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

int main() {
    
  fast_read(a);
  fast_read(b);
  int x, y;
  int d = exgcd(b, P, x, y);
  if (a % d) puts("Angry!");
  else printf("%ld\n", ((long) x * a / d % P + P) % P);
}

时空复杂度$O(\log b)$。