AOJ 12/2

2014-12-02 | [Competitive programming]

1321

枝刈り探索.以下のことをしたら通った:

2455

問題文が読みづらいが,読みやすいページ を見ると 「多項式 f について,f(x) = f’(x) = 0 の最小の正の整数解を求めよ」であることがわかる.

ところで,この条件は「f(x) = 0 の最小の正の重解を求めよ」である.x^n で割ってやって最低次の項を 0 次にすると, a が求める解であるためには a^2 が 0 次の項の約数になってないといけないことがわかる. 適当にやると,0 次の項の平方因子が求められるので,その約数についてのみ調べればよい.

ある数が答えになっているかどうかは,適当に mod をとって 0 になるか確認してやるとよい.

2341

trie を作った後に,根を始状態かつ唯一の受理状態とする NFA を作る. すると,NFA の受理状態列のうち,対応する文字列が辞書順 K 番目になるものを求める問題になる. あとは定数倍最適化