原理：将模数  mod \bmod 分解质因数 p1c1p2c2p3c3⋯p_1^{c_1}p_2^{c_2}p_3^{c_3}\cdots，再将所有参与运算的数按照  mod \bmod 的质因数分解为 v×p1c1′p2c2′p3c3′v\times p_1^{c'_1}p_2^{c'_2}p_3^{c'_3}，其中 vv 为不属于  mod \bmod 质因数的部分，可以直接用 exgcd 求逆元，其余部分在进行乘除运算时直接指数相加减，最后乘在一起就是结果，如果运算完有指数为负则没有逆元，一般使用下（比如求组合数）是不会出现指数为负的。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
int mod = 15;
// ...
int cntp, p[MAXcntp * 2 + 10];
void Dis(int x) {
    cntp = 0;
    for (int i = 2, topi = sqrt(x); i <= topi; ++i) {
        if (!(x % i)) {
            p[++cntp] = i;
            while (!(x % i)) {
                x /= i;
            }
        }
    }
    if (x > 1) p[++cntp] = x;
}
struct Number {
    int v, c[MAXcntp * 2 + 10];
    inline Number(){}
    inline Number(int x) {
        for (int i = 1; i <= cntp; ++i) {
            c[i] = 0;
            if (!x) continue;
            while (!(x % p[i])) {
                ++c[i];
                x /= p[i];
            }
        }
        v = x;
    }
    inline void operator=(int x) {
        memset(c, 0, sizeof(c));
        for (int i = 1; i <= cntp; ++i) {
            c[i] = 0;
            if (!x) continue;
            while (!(x % p[i])) {
                ++c[i];
                x /= p[i];
            }
        }
        v = x;
    }
    inline Number operator*(Number sec) {
        Number ans;
        ans.v = v * sec.v % mod;
        for (int i = 1; i <= cntp; ++i) {
            ans.c[i] = c[i] + sec.c[i];
        }
        return ans;
    }	
    inline Number operator/(Number sec) {
        Number ans;
        ans.v = v * inv(sec.v) % mod;
        for (int i = 1; i <= cntp; ++i) {
            ans.c[i] = c[i] - sec.c[i];
        }
        return ans;
    }
    inline int real() {
        int ans = v;
        for (int i = 1; i <= cntp; ++i) {
            ans *= power(p[i], c[i]);
            ans %= mod;
        }
        return ans;
    }
};

signed main() {
    Dis(mod);
    Number a(36), b(14);
    Number c = a / b;
    printf("%lld\n", c.real());
}