結果
問題 | No.3106 Simple Math Problem 3 |
ユーザー |
![]() |
提出日時 | 2024-10-30 23:45:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 234 ms / 2,000 ms |
コード長 | 666 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,180 KB |
実行使用メモリ | 75,856 KB |
最終ジャッジ日時 | 2025-04-08 22:11:33 |
合計ジャッジ時間 | 8,538 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
def fast(n): ans = 0 x = 1 while min(n, x*x) != n: ans += x * (x-1) * (x+1) // 6 x += 1 lb = x ub = n + 1 k = 1 while k <= n: tub = (n-1) // k tlb = x if tlb > tub: break vlb = k * tub + 1 vub = min(n + 1, k * (tub + 1) + 1) ans += (vub - vlb) * (vub - vlb + 1) // 2 tub -= 1 if tlb <= tub: ans += (tub - tlb + 1) * k * (k+1) // 2 k += 1 for x in range(1, n+1): ub = n lb = min(n, x*x) if lb == ub: break ubv = ub//x ubr = ub%x lbv = lb//x lbr = lb%x ans += x * (x-1) // 2 * ubv + ubr * (ubr+1) // 2 ans -= x * (x-1) // 2 * lbv + lbr * (lbr+1) // 2 return ans n = int(input()) print(fast(n) % 998244353)