結果
問題 | No.2989 Fibonacci Prize |
ユーザー |
👑 |
提出日時 | 2024-12-14 12:48:37 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 991 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 82,472 KB |
実行使用メモリ | 200,012 KB |
最終ジャッジ日時 | 2024-12-14 12:48:46 |
合計ジャッジ時間 | 8,114 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 76 WA * 1 |
ソースコード
n, m = map(int, input().split())if n == 1:ans = m * (m + 1) // 2ans -= m - 1if m >= 3:ans -= m - 3print(ans)exit()if m <= 10:F = [1, 1]while len(F) < m:F.append(F[-1] + F[-2])ans = 0for l in range(m):tot = 0for r in range(l, m):tot += F[r]if tot % n == 0 and tot <= F[m - 1]:ans += 1print(ans)exit()a = 0b = 1cnt = [0] * ntot = 0lst = []F = []while 1:tot = (tot + a) % nlst.append(tot)F.append(a)cnt[tot] += 1a, b = b, (a + b) % nif a == 0 and b == 1:breakC = [0] * nle = len(lst)loop = (m - 1) // lefor i in range(n):C[i] = cnt[i] * loopfor i in range((m - 1) % le):C[lst[i]] += 1ans = 0for c in C:ans += c * (c - 1) // 2a = F[m % le - 2]b = F[m % le - 1]c = F[m % le]if (a + b) % n == 0:ans += 1if b % n == 0:ans += 1if c % n == 0:ans += 1print(ans)