diverta2019 D. DivRem Number 解説[python]

概要

　正の整数Nがあり、以下の条件を満たす整数mの総和を求めよ
　　
　Nをmで割った時の商とあまりが等しい
　N//m = N % m

制約

1<=N<=10**12

考察

Naive な方法を考えると、1~Nまで順に割って確かめれば良いが10**12でTLE

　条件を式に当てはめてみると、N = k*m + k (N//m = kとした時）となる
　N=k * (1+m) で　k はmで割った時のあまりでもあるから 0<=k<=m-1である

　逆に0<=k<=m-1 をみたし、N=k * (1+m) となる２つの整数のくみk,1+m が見つかればそれはm である。
　
　したがってN の約数を列挙してk,N//k が2以上離れているペアを見つければ良い。
　

実装

#!/usr/bin/env python3
def divisor_dif_2_over(n):
    if n == 1:
        return []
    res = []
    i = 1
    while i * i <= n:
        if n % i == 0 and (n // i) - i >= 2:
            res.append(n // i - 1)
        i += 1
    return res


n = int(input())
# print(divisor_dif_2_over(n))
print(sum(divisor_dif_2_over(n)))

次回への反省

　整数問題は式に直して展開するだけで解けることもある。
　式が２つの整数の掛け算で表されたら約数を考える。
　
実装は特に詰まらず。
ここまで書いてn//i をそのままリストにしてサンプルが合わなかったので反省。