Zerojudge e373：一元二次同餘方程式

Zerojudge e373：一元二次同餘方程式

題目大意：給定質數 $p$ 與三個非負整數 $a,b,c$，其中 $0≤ a,b,c ≤ p−1$ 且 $a≠0$，請找出同餘方程式 $ax^2+bx+c≡0$ ($\text{mod}\ p$) 在 {$0,1,…,p−1$} 內的根。

解法：二次剩餘。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LL long long
#define GU getchar_unlocked()
#define PU putchar_unlocked

int in() {
    ...
}

void out(int x, char c) {
    ...
}

int min(int x, int y) {
    return x <= y ? x : y;
}

int max(int x, int y) {
    return x >= y ? x : y;
}

int p, ii;
int A, B, C;
int now = 1;

int get_rand(int l, int r) {
    ...
}

int get_mod(LL x) {
    x %= p;
    return x + (x < 0 ? p : 0);
}

struct ModImag {
    int real, imag;
    ModImag() {}
    ModImag(int r, int i): real(r), imag(i) {}
    ModImag operator * (const ModImag& x) {
        int r, i;
        r = ...;
        i = ...;
        return ModImag(r, i);
    }
};

int power(int d, int up) {
    int ans = 1, mult = d;
    while(up) {
        if(up & 1)
            ans = (LL)ans * mult % p;
        mult = (LL)mult * mult % p;
        up >>= 1;
    }
    return ans;
}

ModImag mower(ModImag d, int up) {
    ModImag ans(1, 0), mult = d;
    while(up) {
        if(up & 1)
            ans = ans * mult;
        mult = mult * mult;
        up >>= 1;
    }
    return ans;
}

void solve() {
    A = in(), B = in(), C = in();
    if(p == 2) {
        bool is = 0;
        if(C % 2 == 0)
            PU('0'), is = 1;
        if(((LL)A + B + C) % 2 == 0)
            printf(is ? " 1" : "1"), is = 1;
        if(is == 0)
            printf("no solution");
        PU('\n');
        return;
    }

    int n = get_mod((LL)B * B - 4ll * A % p * C);
    if(power(n, p / 2) == p - 1) {
        printf("no solution\n");
        return;
    }
    if(n == 0) {
        out(get_mod(- (LL)B * power((LL)A * 2 % p, p - 2)), '\n');
        return;
    }
    if(C == 0) {
        int ans = get_mod(-(LL)B * power(A, p - 2));
        if(ans)
            printf("0 "), out(ans, '\n');
        else
            printf("0\n");
        return;
    }

    int a, time = 0;
    while(1) {
        a = get_rand(0, p - 1);
        ii = get_mod((LL)a * a - n);
        time++;
        if(power(ii, p / 2) == p - 1)
            break;
    }

    int x = mower(ModImag(a, 1), p / 2 + 1).real, x1, x2;
    x1 = get_mod((LL)(-B + x) * power((LL)A * 2 % p, p - 2));
    x2 = get_mod((LL)(-(LL)B - x) * power((LL)A * 2 % p, p - 2));
    if(x1 == x2)
        out(x1, '\n');
    else
        out(min(x1, x2), ' '), out(max(x1, x2), '\n');
}

int main() {
    srand(time(NULL));
    while((p = in()) != -1)
        solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！