Wizards (UVa Live Archive Europe Southwestern 2008)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2306

問題

n次多項式を与えるのでそれが重解を持つかどうか判定せよ。
0<=n<=10

• 30<=係数<=30

解法

重解を持つ条件はf(x)=0かつf'(x)=0となるxが存在することである。なので、gcd(f(x),f'(x))の次数が2以上になるかどうかを調べれば良い。計算をdoubleでやったら誤差死したっぽいので、mod 1e+9+7で計算した。