diverta 2019 で D を modulo にした人

どうも，diverta 2019 で D 問題の sample 2が 999,999 ずれた人です． （C も分岐対処したつもりが，漏らしてたんですけどね．オーバーフローも初体験で動作を知らなかったし大変だった．）

999,999 ずれるのは半分はオーバーフローのせいです．半分は実装のせいです． （ここ，混乱してます・・・オーバーフローが出ていたが該当箇所を忘れたので修正）

オーバーフローの内容

999,999 ずれますが，最後に加算されたのは 1,000,000 です． オーバーフローして，加算値が 999,999 になってます． (N - i) % i == 0 を 1,000,000 は満たしますが答えの条件には一致してません． 要するに，999,999 ずれている人は 1,000,000 の排除が基本方針です．

このエラーが出た人や，moduloでやったがACでない人の解法は

N = int(input())
 
result = 0
for i in range(1, int(N**0.5)+1):
  if (N - i) % i == 0:
    result += (N - i) / i
 
print(int(result))

なのかなあ．と思います． floor(N/m) = N %m を変形させて，(N - m) % m = 0 かなあと思って解きました． 正規の解法は N = k(m+1) なので正しいように思えますが，この解法は少し間違っているようです（出せばわかる）． 薄々気づいていた人もいると思いますが，余剰では k の値が考慮されていないというのが問題です． とりあえず，解決してしまう実装として再度チェック．

N = int(input())
 
result = 0
for i in range(1, int(N**0.5)+1):
  if (N - i) % i == 0:
    temp = (N - i) // i
    if temp != 0 and N // temp == N % temp:
      result += temp
      
print(int(result))

はい，まあ冷静になれば漏れることはあるだろうなあって感じです． これでも AC は取れましたが非常に気持ち悪いです．

漏れる例としては N=9 の時，1, 3, 9 が候補にありますが，答えは8(=9-1)のみです． しかし， (N - i) % i == 0 では，2(=3-1)が答えに浮上します． 他にも，2, 4, 6, 12, 16 等色々なところで，これが起きます． 原因を考えると，(N - i) // i の値が i より大きいときにエラーが起きてます． （小さいケースはfor文の範囲外なので）

で，(N - i) // i > i を N について解くと，N > i ** 2 + i です． これで全部通ります．

N = int(input())
 
result = 0
for i in range(1, int(N**0.5)+1):
  if (N - i) % i == 0 and i ** 2 + i < N:
    result += (N - i) // i
      
print(int(result))

i について解いて，range の範囲を狭めることもできると思いますが それは本気の実装かなんかかなって感じします． i について解くだけなので

import math
N = int(input())
 
result = 0
for i in range(1, math.ceil(((1+4*N)**0.5-1)/2)):
  if (N - i) % i == 0:
    result += (N - i) // i
      
print(int(result))