AtCoder Beginner Contest 190 D - Staircase Sequences【Python】
https://atcoder.jp/contests/abc190/tasks/abc190_d
AtCoder ProblemsでDifficulty: 722、Solve Probability: 35%でした。
解けませんでした。
(A + B)(B - A + 1) = 2NをXY= 2NとしてXYが2Nの約数となることやXYの偶奇が異なるなどということに全く考えが及びませんでした。
# https://algo-method.com/descriptions/84 def calc_divisors(N): # 答えを表す集合 res = [] # 各整数 i が N の約数かどうかを調べる for i in range(1, N + 1): # √N で打ち切り if i * i > N: break # i が N の約数でない場合はスキップ if N % i != 0: continue # i は約数である res.append(i) # N ÷ i も約数である (重複に注意) if N // i != i: res.append(N // i) # 約数を小さい順に並び替えて出力 res.sort() return res N = int(input()) D = calc_divisors(2 * N) ans = 0 for x in D: y = (2 * N) // x if (x - y) % 2 == 1: ans += 1 print(ans)