その2です。今回は難しめです！

例としては、「○○に対して□□を満たす△△が必ず存在することを示せ」という問題があったとしたら、「○○が与えられるので、□□を満たすような△△を出力せよ」に変える、って感じです。

今回の問題はフランスからです。

問題概要

$p$ を3以上の素数とする。

正の整数列 $ a _ 1 \cdots a _ p $ であって、以下の条件を満たすものを一つ出力せよ。

$p \le 10 ^ 5 $

現問題url (France Team Selection Test Day2 p3)

AGC換算で 1000~1300 くらいだと思います(個人の感想)

ヒント1

大体 $2p $ ずつになりそうな、、、？

ヒント2

$a _ i = 2pi+ f(i) $ の形で表せます。

解答

$a _ i = 2pi+ (i ^ 2 \% p) $ が条件を満たします。以下それを示す。

$a _ i $ 相異なること、 $ 2p ^ 2 $以下であることは明らかなので、二つ目の条件についてします。

$ a _ x + a _ y = a _ v + a _ w $ ならば

$ \{ x , y \} = \{v,w\} $ であることを示します。

$ 2p ( x + y - v - w) = (x ^ 2 \%p) + (y ^ 2 \% p)-(v ^ 2 \%p)- (w ^ 2 \% p) $

右辺の絶対値は $2p$ 未満なので、

$x + y = v + w $

$x ^ 2 + y ^ 2 = v ^ 2 + w ^ 2 ~~ (mod p) $

が分かります。前者を二乗して後者を引くと

$ 2 xy = 2vw~~ (mod p) $

$ (2,p) = 1 $ より

$xy = vw ~~(mod p)$

よって、 $ \{x,y\} ,\{v,w\} $ はともに $ \mathbb{F} _ p $ 上の多項式
$f(x) = x ^ 2 - (x + y) +xy $ の解集合なので一致します。

所感

三番級なので流石に難しいですね。
おそらく $2pi + f(i) $ の形に書けばよいというのをなんとなくで当てた後に詰めれれば順当に解けそうです。
しかも素数でわざわざ 3以上ならまあ大体 mod p で見るだろうしね...
あともうちょっとセンスのいいタイトル募集してます！

のいみのいみのいみのいみ