ACL1B
from ACL1
ACL1B
考えたこと
1 + 2 + \cdots + k = k (k + 1) / 2なので問題条件はk * (k + 1) % N = 0
注: mod 2Nが正しい
とりあえず素朴に探索して表示し、パターンを見つける
Nが素数の時はk=N-1
Nが2の累乗の時もk=N-1
異なる素因数に分かれてる時に小さくなる
Nの素因数分解fを求めて最大の
m = max([p ** f[p] for p in f]) を得るmで満たさない残りr = N // mを考える
nm + 1 もしくはnm - 1がrの倍数であるような最小のnを素朴に探す
→これでは問題の求める最小解が得られるとは限らない
方針がダメなのかと思って終了
公式解説
上記条件(に似た条件)を満たす解はCRTで得られる
最大のmについてだけ計算するのではなく、約数全体について行う
Nのある約数mについて、r = 2 * N // mとして
kはmの倍数、k+1はrの倍数、となるkが存在するか？
存在するためにはmとrが互いに素である必要がある
互いに素である場合には中国剰余定理の解の存在に帰着する
約数列挙がO(sqrtN)、各約数についてのCRTがO(logN)なので間に合うらしい
CRTは必要ない
k \equiv 0 \pmod{m}, k \equiv -1 \pmod{r} の時 k = amとすると
am \equiv -1 \pmod{r},
a \equiv -1 \cdot m^{-1} \pmod{r}
というわけで
k = -1 * inv_mod(m, r) * m で良いからCRT version
pythondef solve(N):
from math import gcd
if N == 1:
return 1
ret = N - 1
for n in all_divisor(2 * N, includeN=False):
m = (2 * N) // n
if gcd(m, n) != 1:
continue
k = crt(0, n, -1, m)
if k < ret:
ret = k
return retnon-CRT version
pythondef solve(N):
if N == 1:
return 1
factors = factor(2 * N)
num_factors = len(factors)
if num_factors == 1:
return N - 1
factors = [p ** factors[p] for p in factors]
ret = N - 1
for i in range(2 ** num_factors - 1):
prod = 1
j = 0
while i:
if i & 1:
prod *= factors[j]
j += 1
i >>= 1
rest = (2 * N) // prod
k = (-pow(prod, -1, rest) * prod) % (2 * N)
if k < ret:
ret = k
return retうーむ AC 21 TLE 21
素因数分解が遅いのか、束ね直すところが遅いのか
あとpowがmod Pでの逆元を求められるのはPython3.8からの割と新しい機能なのでPyPyでは動かなかった
ValueError: pow() 2nd argument cannot be negative when 3rd argument specified 2Nが正しい話
Nが6の時1+2+3 = 6なので3が解
N だと 2 * 3 mod 6 = 0で2, 3が互いに素なので2と答えてしまう
2N だと 2, 6は 互いに素でなく、3, 4の3を答えて正解
Related Pages
- →past5h×abc184e×past4j×past4k×abc175d×ARC106×abc164d×素因数分解を O(n^(1/4)) でする×abc189×abc190e×abc194f×atcoderのpythonでmemoryerrorを出すとreになる×agc048×abc179d×深さ優先探索×aoj_grl_5_c×arc107×agc044a×past2n×past3o×頂点を塗るのか辺を塗るのか×past4m×abc178f×abc192×abc191→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]