Connection 解题过程

· · 个人记录

从现在开始我就要把我的解题过程写下来，数学方面不写不行了/kk

link

\begin{aligned} &n = p \times q\\ &65537 \times d \equiv 1 \pmod{(p - 1) \times (q - 1)}\\ &m \equiv c^{d} \pmod{n} \end{aligned}

因为 n 和 m 都很好求，所以难点在于 65537 \times d \equiv 1 \pmod{(p - 1) \times (q - 1)}。

原式可化为：

65537 \times d + (p - 1) \times (q - 1) \times k = 1

发现 65537 = 2^{16} + 1 是个质数，可以分为两种情况：

理论存在，实践开始（（（

Code：

#include <bits/stdc++.h>
namespace VividCycle {
    #include <bits/stdc++.h>
    #define getchar gc
    #define putchar pc
    #define fu(i, l, r) for(int i = l; i <= r; ++i)
    #define fd(i, l, r) for(int i = l; i >= r; --i)
    #define fo(i, v) for(const auto& i : v)
    using namespace std;
    typedef __int128 ll;
    typedef unsigned long long ull;
    static char buffer[1 << 20 | 1]; static int outp = -1;
    void flush() {fwrite(buffer, 1, outp + 1, stdout), outp = -1;}
    void pc(const char& ch) {if(outp == (1 << 20)) flush(); buffer[++outp] = ch;}
    char gc() {static char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf; return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1000010, stdin), p1 == p2) ? -1 : *p1++;}
    template<typename T> void read(T& x) {x = 0; int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') f *= ((ch == '-') ? -1 : 1), ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f;}
    template<typename T, typename ...Args> void read(T& x, Args& ...args) {read(x), read(args...);}
    void write(const char& ch) {putchar(ch);} void write(const char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);} void write(char s[]) {int len = strlen(s) - 1; fu(i, 0, len) putchar(s[i]);}
    template<typename T> void write(T x) {static char obuf[1 << 8]; static int p; p = 0; if(x < 0) x *= (putchar('-'), -1); if(!x) {putchar('0'); return;} while(x) obuf[++p] = x % 10 ^ 48, x /= 10; while(p) putchar(obuf[p--]);}
    template<typename T, typename ...Args> void write(T x, Args ...args) {write(x), write(args...);}
}
using namespace VividCycle;
ll t, f, c, p, q, m, e, n, d, x, y, g;
void Exgcd(ll a, ll b, ll& x, ll& y) {
    if(!b) x = 1, y = 0, g = a;
    else {
        Exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}
ll ksm(ll x, ll y) {
    ll ret = 1;
    while(y) {
        if(y & 1) ret = ret * x % n;
        x = x * x % n;
        y >>= 1;
    }
    return ret;
}
int main() {
    read(t);
    while(t--) {
        read(f);
        if(f) {
            read(c, p, q);
            n = p * q;
            Exgcd(65537, (p - 1) * (q - 1), x, y);
            d = (x % ((p - 1) * (q - 1)) + ((p - 1) * (q - 1))) % ((p - 1) * (q - 1));
            write(ksm(c % n, d), '\n');
        }
        else {
            read(m, e, n);
            write(ksm(m % n, e), '\n');
        }
    }
    flush();
    return 0;
}