P2613 【模板】有理数取余

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int p = 19260817;
 5 inline ll read() {
 6     ll res = 0;
 7     char ch = getchar();
 8     while(!isdigit(ch) and ch != EOF)
 9         ch = getchar();
10     while(isdigit(ch)) {
11         res = (res << 3) + (res << 1) + (ch - ‘0‘);
12         res %= p;
13         ch = getchar();
14     }
15     return res;
16 }
17 void exgcd(ll a, ll b, ll &x, ll &y) {
18     if (b == 0) x = 1, y = 0;
19     else exgcd(b, a%b, y, x), y -= a/b * x;
20 }
21 int main() {
22     ll a = read(), b = read();
23     if (b == 0) {
24         puts("Angry!");
25         return 0;
26     }
27     ll x, y;
28     exgcd(b,p,x,y);
29     if (x < 0) x += p;
30     printf("%lld\n",x*a%p);
31     return 0;
32 }