pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

yukicoder 550: 夏休みの思い出(1)

https://yukicoder.me/problems/no/550

解法

x3+ax2+bx+c=0 を解く前に x3+ax2+bx+c≡0 (mod 33331) で解く。これは全探索で解くことができ、解の個数が 3 個以下であることが保証されている。

得られた解を α,β,γ とすると、元の方程式の解は α+33331k,β+33331k,γ+33331k の形で表せる。解の範囲が分かっているため、こちらも全探索できる。

#include <iostream>
#include <set>

int main() {
    long long a, b, c;
    std::cin >> a >> b >> c;

    constexpr int MOD = 33331;
    std::set<long long> ans;
    for (__int128 i = 0; i < MOD; i++) {
        if ((i*i*i + a*i*i + b*i + c) % MOD == 0) {
            for (__int128 j = i - MOD*MOD; j <= MOD*MOD; j += MOD) {
                if (j*j*j + a*j*j + b*j + c == 0) ans.insert(j);
            }
        }
    }

    for (long long x : ans) {
        std::cout << x << ' ';
    }
}

python3 (153 bytes)

a,b,c=map(int,input().split())
P=33331
f=lambda x:(x+a)*x*x+x*b+c
print(*sorted(j for i in range(P) if f(i)%P==0 for j in range(i-P*P,P*P,P) if f(j)==0))

解の範囲が狭いことが分かっていれば、より高次の方程式に対しても同じ方法が適用できる。