引用
（引用）
問題文
整数からなる公差 1 の等差数列のうち、総和が N であるものはいくつあるでしょうか？
制約
1≤N≤10^12
N は整数
AtCoder Beginner Contest 190 D – Staircase Sequencesより引用
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
12
出力例 2
4
[1,2]
[3,4,5]
[−2,−1,0,1,2,3,4,5]
[−11,−10,−9,…,10,11,12]
の 4 個です。
考えてみました①
①まず深く考えずにforでまわす
②正の数だけで考える。１スタートの数列なら０スタートが、２スタートなら−１スタートが対極に存在するから、最後にcount×２
③ i=１〜１２でまわす
④ j= i 〜１２でどんどん加えていき、小さいうちはpass、==でcount、大きくなってbreak
N = int(input())
count = 0
for i in range(1,N+1):
total = 0
for j in range(i,N+1):
total += j
if total < N:
pass
elif total == N:
count += 1
elif total > N:
break
print(count*2)⑤当たり前だけど、『1≤N≤10^12』でforを２回まわすとTLE
計算量がO(n^2)になるのか・・・
考えてみました②
①まず正の数だけで考える。１スタートの数列なら０スタートが、２スタートなら−１スタートが対極に存在するから、最後にcount×２
②下のforが本命だけど、rangeでどこまでやるか（b+2）を評価する
１から順番に足して行っているから、最大のbになるはず
N=12ならbは5かな
③3,4,5を棒グラフで書くと、1,2,3の三角屋根部分と、2,2,2の長方形部分に別れるはず
12から1を引いて、1で割れればそれは、12そのもの
12から1,2を引いて、2で割れない
12から1,2,3を引いて、3で割れるので、それは3,4,5
12から1,2,3,4を引くともう割れない
(N2 – i(i+1)) % (i*2)って書いているのは、全項２倍しているから
N = int(input())
b = 0
#下のforが本命だけど、rangeでどこまでやるか（b+2）を評価する
#１から順番に足して行っているから、最大のbになるはず
#N=12ならbは5
for a in range(N):
if a*(a+1) > N*2:
b = a
break
#3,4,5を棒グラフで書くと、1,2,3の三角屋根部分と、2,2,2の長方形部分に別れるはず
#12から1を引いて、1で割れればそれは、12そのもの
#12から1,2を引いて、2で割れない
#12から1,2,3を引いて、3で割れるので、それは3,4,5
count = 0
for i in range(1,b+2):
if (N*2 - i*(i+1)) % (i*2) == 0:
count += 1
print(count*2)④サンプル７だけエラー出て何故かわかりません
考えてみました③
解説読んだら理解した
整数問題であることを利用するみたい
ここで初めて知ったけど約数全探索ってあるみたいね
#約数列挙（divisor）
def div(M):
div_set = set()
for i in range(1,int(M**0.5)+1):
if M % i == 0:
div_set.add(i)
div_set.add(M // i)
return div_set
print(div(12))#{1, 2, 3, 4, 6, 12}
2Nの約数を列挙して、
①だと複雑化するから、
②で2N//n（当たり前だけど割れる。/でなくて//に注意）が正の数で、
2N//n – nが正でも負でも、奇数ならａが存在する
D = div(2 * N)
ans = 0
for n in D:
m = (2 * N) // n
if (n - m) % 2 == 1:
ans += 1
print(ans)追記
最初のやり方のやつ、何度か調整した結果、サンプル７も突破出来ました。
追加したのは（n+2）で評価した部分で、N=6だけがずれる。
(N×2 – i×(i+1))が負の数になる事を想定していなかった・・・
N = int(input())
n = 0
for a in range(N):
if a * (a + 1) > N * 2:
n = a
break
count = 0
for i in range(1, n + 2):
if (N * 2 - i * (i + 1)) >= 0 and (N * 2 - i * (i + 1)) % (i * 2) == 0:
count += 1
print(count * 2)修正してようやくACでました。
ただし、時間がかかり過ぎました。
コメント