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