有理数取余模板

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const ll p = 19260817;

//用于求 b * x1 ≡ 1 (mod p)
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll getres(ll a, ll b)
{
    ll x,y;
    exgcd(b,p,x,y);
    ll x1 = (x+p)%p;
    return x1 * a % p;
}

// 求有理数(a / b) % p的值
// 等价于 求 b * x ≡ a (mod p)
// 等价于 先求 b * x1 ≡ 1 (mod p) 再两边乘a
// 答案为a * x1
int main()
{
    ll a, b;
    cin >> a >> b;
    
    if (b % p == 0) puts("无解");
    else
    {
        ll res = getres(a, b);
        cout << res;
    }
    
    return 0;
}