diverta 2019 Programming Contest D - DivRem Number
500点問題が自力で通せました！嬉しい！（800は通せなかったけど）
したこと
一旦入力例1を書き出してみた！
数字…(商,余り)のように書いてみると
1…(8,0)
2…(4,0)
3…(2,2)
4…(2,0)
5…(1,3)
6…(1,2)
7…(1,1)
8…(1,0)
という風になりました。
数学タイム
この場合、商と余りが同じなのは3と7の場合です。で、よ〜〜く考えてみると
xで割った商と余りが(a,a)になる自然数xは、必ずa+1以上である。
ということが分かります。なぜなら、xで割った時の余りは必ずx未満になるからです。
(例) 商と余りが(2,2)になる数字xは必ず3以上です。なぜならxが2以下だと割った余りが1以下になるので。
そう考えると、xは必ず(a+1)以上なのでNはa回割り切られるために(a+1)*a以上になる必要があります。(a+1)*aがNを超えたらそれ以上は無理です。for文でaを1から回していくと、だいたい√N回くらいのループになります。
Nが10のとき、商と余りがともに2となる自然数xは、(10-2)/2 = 4と求められます。商と余りがともにaとなる自然数xがあるかどうかの判定は、だいたい(N-a)%a == 0でできます。%を/に変えれば、xが求められます。
WAる
よっしゃいけるわ…！と思って出してみたものの、1問だけWA。これはコーナーケースか？と思ったので1から順番に試していくと、3辺りで間違っているのが分かった。一回一回のxを求めた時に本当に商と余りが合っているのかどうかのフィルターをif文でかけてみると、上手くいきました。（こういう対策方法良くなさそう…）
