メモ

yukicoderでゆるふわgolf

Project Euler 401-450 解説

これの続き
sugarknri.hatenablog.com

何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ

401
主客転倒でO(√N)
D - Sum of Divisors
凸包テクでO~(N^(1/3))になるらしい。1乗のときの解説はここ
凸関数に囲まれた領域の中の格子点の凸包の頂点を列挙する一般的なテク - 競プロをはじめた家事手伝いロボットのブログ

402
定義からM(a,b,c)|gdc(f(1)-f(-1),f(2)-f(-2))であり、ある定数Xが存在してgdc(f(1)-f(-1),f(2)-f(-2))|Xなので、S(n)はn%Xごとにn/Xの3次式

403
数学をすると交点の座標が整数になることがわかるので、変数変換してすべてそれで考えることにすればO(√N)で計算できる式になる

404
数学をかなり頑張るとa,b,cが満たすべき数式が出てくる。直交座標よりも極座標で考えた方が簡単
でてきた式を整理すると「p^2+q^2=hogeの有理点を列挙せよ」といういつものやつに帰着できて解ける

405
実験してエスパー
証明は「辺を共有する2つの畳の位置関係は4種類しかないので、それらが次の1ステップでどうなるか観察する」

406
答えを二分探索
「二分木の左に潜るにはコストa、右に潜るにはコストbかかる。コストx以内で到達できる頂点の個数は?」

407
(Z/nZ)^*の構造を知っていますか?
CRTで素ベキの場合に帰着。mod 2^eでe>2のときだけ2解あることに気を付けて、あと全探索

408
Y - Grid 2

409
dp[m]=山の個数がmのとき条件を満たす組み合わせ
で実は求まる。遷移は……?

410

411
セグ木で平面走査

412
知識ゲー
Hook length formula - Wikipedia

413
桁DP。gcd(10,d)!=1のときに注意する
テクい状態の持ち方をするとO(N^2 2^N)にもなる。
数Xが条件を満たす必要十分条件は、「∃! i (∃j s.t. X[i:j]はNの倍数)∧(∀i'≠i ∀j X[i':j] はNの倍数でない)」である
(読者への宿題:∃!i∃jのところが∃!i∃!jでなくてよいことの証明)
この条件を満たす数はiを固定するごとにdisjointであるから、iごとにO(N 2^N)で数え上げられる。
threadには「NFAをこねこねするとこのDPになる」と書かれているが、よくわからず。
関連:NFAをDFAに変換するやつ
Powerset Construction DPについて • knshnbのブログ

414

415

416
DP+行列累乗
俺の中ではこれの類題としてジャンルになっているが、このDPに名前がついているのを聞いたことがない
No.213 素数サイコロと合成数サイコロ (3-Easy) - yukicoder

417
10の(\mathbb{Z}/N\mathbb{Z})^\timesでの位数を求めてください、という問題なので399のより簡単なバージョン
O(NlogNloglogN)くらい?

418
制約がN≦10^14ならここに
No.376 立方体のN等分 (2) - yukicoder
a,b,cいずれもをN^(1/3)くらいにとるのが最適なので、N^(1/3)付近の約数をあらかじめ列挙してaを枝刈り全探索

419
Look-and-say sequence - Wikipedia
頑張って観察すると自力でも気づけるらしいが、それはもうコンウェイなんだよな

420
2×2行列の平方根という概念を使ってもいいが、適当に数式をガチャガチャやるだけでも解ける。
Square root of a 2 by 2 matrix - Wikipedia

421
「n^15=-1 mod mを解いてください」という問題なので、407と同様。
原始根を求めなくても、x^5+1が因数分解できるので、平方根だけで直接計算することもできる

422

423
「n回投げてちょうどm個」は一発で計算できるので、最後の1回を追加してどうなるか差分更新をやるとO(NlogN)

424
96の数独のように手でも解けます
俺はSAT solverを用意するのを面倒がってIP solverに投げたがそれでも解ける
普通にバックトラックDFSでも解けるっぽい?

425
UF
ダイクストラでも解ける

426
問題タイトルが答え
「箱玉系」でググって出てくる日本語論文に目を通すと答えが書いてあるが、証明はわからず
十分間隔が広い箇所で2つに分けて再帰的に処理することでも解けるらしいが、証明はわからず

427

428
概念はこれ
Steiner chain - Wikipedia
数式はこれを使うのが簡単
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1843-17.pdf
証明はこれでできるらしい
反転幾何学 - Wikipedia
あとは丁寧に式を整理すると空間O(N)時間O(NlogN)までは簡単
ちょっと変な形をしているが、少し考えるとい つ も のに帰着できて、O~(N^(2/3))になる。

429
自明
ルジャンドルの定理など
O(NlogN)。線形篩でO(N)になる?

430
期待値の線形性
二項定理
小さすぎる値は無視して近似してよい。近似を使わずに(計算精度を度外視すると)O(M^2)で求めることもできる

431
気合で数値積分+二分探索

432
totient sumとほぼ同じ
dirichlet級数の練習問題だと思うこともできる
いずれにせよO~(N^(2/3))

433

434
グリッドを見たら二部グラフだと思え、の格言に従って考察すると解ける
O(N^4)

435
行列累乗やるだけ
CRT+pisano periodでも解ける

436
2変数積分方程式を立てて頑張って計算すると手ですべて解ける
確率密度関数を直接求めに行く方針でも手で解ける

437
原始根よりもfibonacciの条件の方が強いので、fibonacciの条件を満たす数を求めてから、それが原始根かどうか判定する
mod_sqrt

438

439
最終的にきれいな式がでてきて い つ も の でO~(N^(2/3))になる
いろいろ考え方はあるが、σ(ij)が乗法的ではあるが完全乗法的ではないことから、そこの違いを解消するように包除原理をするとよい。
具体的には\sigma(p^ap^b)=\sigma(p^a)\sigma(p^b)-p\sigma(p^a/p)\sigma(p^b/p)なので、これをp partごとに考えて包除すれば\sigma(ij)=\sum_{d|\gcd(i,j)}\mu(d)d\sigma(i/d)\sigma(j/d)を得る。
他にも例えば \sigma(ij)=\sum_{x|i,y|j}f(x,y)なるfを気合で求めるなど、いろいろやりようはあるのでまあやれば解ける

440
T(n)ではなくfibonacci数だとどうなるか考えると、Tも似たような漸化式を持つので似たような性質を持つだろうと予想できる
あとはこまごました計算をすればOK

441
coprimeと書いてあるので約数包除
o(NlogN)にするには多くの方針で1/xy=(1/x+1/y)/(x+y)を使ってうまく式変形することが求められる
調和数を適当に近似してO(1)で求めることにすれば い つ も の でO(N^(2/3))にもできる
包除で引き算やってて精度保証を机上でやるのはもう無理。単にO(Nε)で見積もっても、拡張倍精度でεは2^-63≒1e-19、N=1e7、要求精度が1e-11だから結構怪しい。めちゃくちゃ

442
桁DP+にぶたん
「与えらえた文字列を部分文字列に持つような長さNの文字列を求めてください」ならKMPなりtrieなりSAなりで適当にやるとDPできる
あとはそれの直積を状態に持てばよい
制約が小さいのでかなり適当にやっても解けるらしい

443
gcd=1のところをまとめて処理すると実はめちゃくちゃ高速になる
計算量は謎

444
最適な戦略がわかれば、E(n)を求めるパートは期待値の線形性典型
E(n)からSk(n)を求めるパートは適当に近似計算すればよい

445
関数方程式を整理するとa,bが満たすべき条件が得られる
a,a-1が互いに素であることに注意すると、aとしてあり得るものの候補が決まり、bが満たすべき条件もわかる
あとは差分計算。計算量は雑にやるとO(NlogNlogMOD)、logMODを落とすいつもの工夫をするとO(NlogN+NlogMOD)にできる

446
n^4+4が整数係数の範囲で因数分解できるとかいう受験典型テク
あとは445でした考察と2次式の篩をすればOK

447
multiplicativeなので3/4乗、普通に約数包除すれば実は1/2乗
ゼータ関数で書けるので2/3乗にもなるが、約数包除の立式を経ずにたどり着くのは難しそうに思える

448
gcdの値ごとに和を取ることにすると、ほぼtotient sumになる。O~(N^2/3)

449
気合で座標計算したり、解析学の定理を使って頑張ったり、Minkowski–Steiner formulaを使ったりと、厳密解を求める方法はいろいろ解法はあるらしいが、適当に点を取って数値計算するのが一番簡単っぽい

450

特性多項式O(N^3)

自力で発明したのでメモ。たぶん既知のアルゴリズムと同じ?
ref: ABC323G

\begin{pmatrix}
 *-x & * & * & *\\
 * & *-x & * & *\\
 * & * & *-x & *\\
 * & * & * & *-x\\
\end{pmatrix}
これの行列式を求めたい。ところでこれを
\begin{pmatrix}
 *-x & * & 0 & 0\\
 * & *-x & * & 0\\
 * & * & *-x & *\\
 * & * & * & *-x\\
\end{pmatrix}
というような、下三角+余分に斜め1列の形にできれば、行列式の定義通りにN!項の和をとるやつを
dp[x][y]=x行目までの選び方を決めて、選んでない列がy列目(1≦y≦x+1)であるときの、行列式への寄与
でDPできる。これは状態数O(N^2)、遷移数各O(1)、遷移の計算がO(N)(高々N次の多項式同士の加減と、高々N次と1次の多項式の積の計算が定数回)なので全体でO(N^3)

下三角っぽく変形するのは簡単で、まず2列目を使って3列目以降を掃き出す
\begin{pmatrix}
 *-x & * & 0 & 0\\
 * & *-x & *-*x & *-*x\\
 * & * & *-x & *\\
 * & * & * & *-x\\
\end{pmatrix}
そうすると2行目の3列目以降にxが増殖するので、これを3行目以降を使って相殺する
\begin{pmatrix}
 *-x & * & 0 & 0\\
 * & *-x & * & *\\
 * & * & *-x & *\\
 * & * & * & *-x\\
\end{pmatrix}
すると1行目が掃き出せたのであとは同様にやる
気持ちとしてはこれと同じ。
ABC220Ex O(N^3)解法 - メモ


おわりです

Project Euler 351-400 解説

これの続き
sugarknri.hatenablog.com

何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ

351
Dirichlet convolutionでO~(N^(2/3))
Dirichlet 積と、数論関数の累積和 | maspyのHP
これくらい単純ならDirichlet級数に思いを馳せなくても普通にDPだと思うこともできる
トーティエント関数$\varphi(i)$の和$\sum_{i=1}^{N}{\varphi (i)}$を$O(N^{2/3}(\log\log{N})^{1/3})$で求める Wiki - yukicoder
最近中国奥地でO~(N^0.5)が開発されたらしい(未確認)
https://twitter.com/EI_Captain/status/1678956489468428289

352
DPでT(N,p)がO(N^2)

353
大円距離 - Wikipedia

354
格子が正方形の問題は233で見た。これはZ[i]で素因数分解する問題だった。
格子が六角形だとZ[ω]で素因数分解する問題になる

355
Set packing - Wikipedia
IPなので、IP solverに投げると解ける

356
318で見た
証明は増減表を書くとわかる

357
予め素数を列挙しておいて、dでループすると調和級数でO(NlogN)

358
Cyclic number - Wikipedia
この性質を持つ数が1/pの形に限ることをちゃんと証明しましょう。あとは自明

359
実験

360
mod2を考えて定数倍削減
主客転倒。x座標の値がiであるような点の個数が各iでわかればよく、233と同じ

361

362
DP[i][S]=i以下の数のみで、S以下の数を分解する方法の数
とすると素数カウントと同じDPになるのでO(N^(3/4))

363
ベジェ曲線 - Wikipedia
曲線のx,y座標がtの3次式、vの1次式で書けることがわかる。
面積はvの2次式で書けるので、求めるvは一意に定まる。
曲線の長さは∫√(tの4次式)dtの形になるので数値積分

364
O(N)
ステップ1で選べる席が全て埋まった状態が与えられたとき、残りを埋める方法が何通りあるかは簡単。
ステップ1で選べる席が全て埋まった状態が与えられたとき、その埋まり方になる方法が何通りあるかは簡単。
ステップ1で選べる席が全て埋まった状態とは?

365
Lucasの定理+CRT

366
O(logN)
Fibonacci nim - Wikipedia

367
吸収マルコフ連鎖の期待値を求めるいつもの問題。状態数を11!から減らす。
ソートアルゴリズムの気持ちになるとfunctional graphが同型なら状態として等価なことは明らか

368
桁DP。かなりびっくり
Kempner series - Wikipediaに"Schmelzer and Baillie found an efficient algorithm for the more general problem of any omitted string of digits. "と書いてあり、ここに解法が載っている。

369
bitDP
DP[i][n][S]=1〜iまでの4i枚からn枚選んで、n枚から相異なる数を選んだときのマークの集合({0,1}^4)としてありえるものの集合(2^({0,1}^4))がS
スートがC種、数がSまでとして、O(2^2^C*2^C*S*N)
対称性を考慮してさらに改善できるらしいが、頭を使わずに済むのはこのあたりまでか。

370
丁寧に考察すると、これになる
約数包除原理 - メモ
O~(N^(2/3))
制約がでかいのでO(N^(3/4))だとちょっと時間がかかる

371
(1,999),(2,998),…のペアを引く問題だと思うと、dp[n]=すでにn枚見たときの残りの期待値、というDPができそう。
あとは0と500を適切に扱えばOK

372
floor(y^2/x^2)が取りうる値の範囲は(N/M)^2以下なので、
それぞれについて傾きを有理数近似してsum_of_floor_of_linear

373

374
O(N^0.5)
実験
証明は「そうでないなら変更しても損しない」

375
周期性
Rを全探索して最大長方形みたいなことをしてもいいし、主客転倒してもいい
周期性をもつという事実からM(nq+r)がrを固定するごとにqの2次式になることがわかるので、愚直+多項式補完でもいい。

376
挿入DP
目を座圧して持つとさらに加速する

377
桁DP+行列累乗

378
nとn+1は互いに素なのでdTを求めるのは簡単
残りは真ん中を全探索するいつもの

379
\sum_{x\leq y, {\mathrm gcd}(x,y)=1}\frac{N}{xy} みたいなものが求めるもの
約数包除すると∑N/(xy)みたいなものを求めたくなって、これを「(x,y,z)の組でxyz≦Nとなるものはいくつ?」みたいに読み替えて、x,y,zの大小関係について丁寧に場合分けすると愚直がO(N^(2/3))になる。
Dirichlet級数で解釈して一発でできるかはわからず。floorが入ってるのでどのみち言い換えをしないと難しそう

380
行列木定理
scipyに丸投げすると解いてくれる
実はきれいな式が存在する

381
ウィルソンの定理
S(p)=-3/8なのでpのmodで適当に場合分けすると1次式になり、いつものでO(N^(2/3))になる
……threadにはO(N^0.75)しか書かれてないけど、なるよね??

382
与えられたsetが条件を満たすための必要十分条件はmax < sum-max
S[n]を使うかどうかで再帰的に場合分けすると漸化式が得られるのであとはいつもの

383
桁DP
O( (logN)^2)

384

385

多分これ
Marden's theorem - Wikipedia


386
Antichainの最大サイズを求めたいので、Dilworthの定理を思い出しつつ、2次元の場合に思いを馳せると斜めに切るやつを思いつけ、一般の次元でもそれが答えになることがわかる。
あとはosk_a法でO(NlogN)
いつものDPでO~(N^(3/4))だかO~(N^(2/3))でも解ける

387
DFS+ミラーラビン

388
351の3次元版なので、351と同様に解ける

389
算数をすると手で解ける
もちろんDPをしてもいい

390
ヘロンの公式を使うと一般Pell方程式になる
実はこの形の場合、初期解が自明なものに限ることが示せるので、適当にやっても解ける
初期解が自明なものに限ることの証明は自明ではない

391

392
目的関数が凸なので、山登りのようなことを収束するまでやればよい

393
連結性DP
289などでやった

394
積分方程式を立てて解くだけ
Cauchy–Euler equation - Wikipedia
積分方程式数値計算で解こうとすると精度が厳しいと思う(俺は最後の1桁が求められなかった)

395
適当に端っぽいところだけ持ちながらやれば解ける
厳密にやるには考察が必要。i回目のイテレーションで追加される正方形のサイズはi+1種類であり、同じサイズの正方形は同じ向きになるので、サイズごとに座標を持てばO(iter^2)

396
k進法で考えたときの下の桁から消していけばよい
べき乗のmodをいい加減に扱っても正しい答えが得られてしまうので要注意

397

398
2番目ではなく1番目なら主客転倒やるだけ(例:表が出るまでコイントスするときの回数の期待値は?→1+1/2+1/4+…=2)
2番目のときもほぼ同じ
ところでFPSで解釈しても解ける。期待値を求めるというのは実質数え上げなので。

399
問題文にヒントが書いてある
No.3038 フィボナッチ数列の周期 - yukicoder

400
DP
Hackenbush - Wikipedia

続き
sugarknri.hatenablog.com

Project Euler 301-350 解説

これの続き
sugarknri.hatenablog.com

何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ

301
Nimの必勝法を知っていますか?

302
上からDFS

303
BFSやるだけ
D - Small Multiple
桁数を2倍にしたときどうなるかのチェックを挟むと早くなるらしい
値の分布がランダムならexpectedでO(√N)になるのはわかるが、実際のところはよくわからず

304
前半:区間篩なりミラーラビン
後半:fib[n]はO(logn)で求まるが、fib[10^14],fib[10^14+1]さえ求めたらあとは愚直でもオーダーは同じ

305
切れ目がどこにあるか考える

306
grundy数を知っていますか
実験

307
余事象

308
https://en.wikipedia.org/wiki/FRACTRAN
brainf*ckの読解と頭の使い方は同じ。高級言語アルゴリズムに変換して考える

309
直角三角形が見えますね

310
grundy数を知っていますか
不等号の制約があるのでいい感じに1/6にする必要がある
ABC288Hは似て非なる問題

311

312
算数
実験+エスパーでも解けなくはない

313
前半は算数パズル
後半はpを全探索
実は答えは単純な形になってい つ も の でO(N^(2/3))

314
\max_S \frac{\sum_{i\in S}A_i}{\sum_{i\in S}B_i} を求める問題なので、答えを二分探索

315
やるだけ
10^10^4以下の整数すべてとかでも1分で解けるはず(1手だけ真面目にやる)

316
マルコフ連鎖なので行列計算するとO( (logn)^3)でg(n)が求まる
KMP+DPでO(logn)
PGBattle2021かつおぶしD

317
放物線群の包絡線を求めてその回転体の体積を計算する問題
ゴリゴリの数学

318
古くはGCJ2008の時代から競プロ文脈でも無限回既出
線形漸化式の一般項の話をしていると思うこともできるし、2次方程式の解と係数の話をしていると思うこともできる
ただし今回の問題の場合、その前段階で十分条件が必要十分であることをいうのはかなり非自明で難しい。例えばこれを参照
https://sci-hub.se/https://doi.org/10.1007/s000130050442

319
3番目の条件でとりあえず変数分離テクして、maxを決めると実は全部決まる。
残りはい つ も のでO~(N^(2/3))

320
Legendreの定理を使いつつで二分探索すると求まる
二分探索ではなくp進で上の桁から決めていく感じにすると桁ごとにO(1)になるので素因子1つあたりO(log i)、iあたりO(ω(i)log i)になる
ω(i)=O(loglog i)だったはずなので、全体でO(NlogNloglogN)

321
直感的な操作をすると最短になるので、M(n)をnの式で書くのは難しくない
残りはPell方程式

322
一般には高速に解けないが、N,Mが特殊な性質を持つので解けるというタイプのやつ
10ではなく2ならLucasの定理で桁DPやるだけ。
実はmod 2^40でありえる値が十分少ないのでDPするまでもなく全探索できる

323
33状態のマルコフ連鎖だと思ってもいいし、期待値=∑(n回目の操作をする確率)だと思ってもいい。
有限和の形の閉な式もある。なにをやっても解ける

324
行列累乗
雑にやると512状態、parityを考慮すると126状態、回転・反転などを考慮すると23状態まで減らせる

325
実験をすると法則がわかる。証明は簡単
残りは実質floor sumみたいなものなので、うまく再帰すると求まる
軸を入れ替える方ではなく、SB木で分解するみたいなやつの方
計算量はO(logN)

326
実験すると法則がわかる。残りはZero-Sum Rangesやるだけ。O(M)

327
Cを固定してRが小さい方から考える。Cを固定するごとにM(C,R)はO(R)

328

329
DPやるだけ。分母が小さいので数え上げの問題だと思って解けば良い
マスの数をN、ジャンプ回数をTとしてO(NT)

330
一般には高速に解けないが、MODが特殊なので解けるというタイプのやつ
漸化式を作ってにらむ

331
まずはいくつか手で解いてみると解法がわかる
理詰めでやるなら、「1マスだけをflipさせることはできるか?」みたいなことを考えるとよい
残りのパートは一般にはO(N^2)。今回は黒い部分が特殊な形をしているので頑張ると線形時間になる

332
球面幾何学。やるだけ
対称性を考慮するとかなり早くなる

333
N=\sum_{i=1}^{k}2^{A_i}3^{B_i}がvalid partitionのとき、(A_i,B_i)をソートして、A_iを狭義単調増加、B_iを狭義単調減少にできる。\mathrm{ord}_2(N)=\mathrm{ord}_2(\sum_{i=1}^{k}2^{A_i}3^{B_i})=A_1なのでA_1は一意。B_1を全探索してメモ化再帰すればO(NlogN)で解ける。
実はB_1を全探索することなくvalid partitionを1つ求めることはできる。2^{\mathrm{ord}_2(N)}3^e\leq N...(*)を満たすような最大のeとする。N'=N-2^{\mathrm{ord}_2(N)}3^eとおき、N'に対して同様の手順で再帰的にvalid partitionを求める。ord_2(N')>ord_2(N)と(*)から、この再帰アルゴリズムで構築されるN'のvalid partitionは、(ord_2(N),e)を加えてもvalid partitionである。証明終わり
この貪欲アルゴリズムと最初に述べた全探索アルゴリズムを比較することで、Nのvalid partitionが一意であるための必要十分条件は、「eを貪欲にとらなかった場合にはN'にはvalid partitionが存在しない」かつ「eを貪欲にとった場合にはN'のvalid partitionが一意である」とわかる。
よって貪欲アルゴリズムの手順を逆に回す、すなわちvalid partitionが一意な奇数N=\sum_{i=1}^{k}2^{A_i}3^{B_i}から、適当なa>0, b>B_1を用意して、2^aN+3^b< 3^{b+1}であって3の最大指数がb未満であるvalid partitionが存在しないものへ遷移することで、valid partitionが一意な奇数のみへ遷移していくことができる。
計算量はO(N^0.8)とかO(N^0.631)とか言われているがよくわからず。
さらに、今回は2を固定して3を貪欲したが、3を固定して2を貪欲することもでき、この2つのvalid partitionが一致することがuniqueであることの必要十分であるらしいので、polylog解けるらしいが、"It is fairly easy to check that ..." と書かれている部分の証明がわからないので正当性は理解できてない

334
GCJ2010で既出 https://www.acmicpc.net/problem/12560
終了条件を満たす状態に、1つ豆を加えた状態から操作を開始して、再び終了条件を満たす状態に至るまでに何が起こるかを観察することで、O(豆の個数)で解ける
実はO(皿の個数)でも解ける。終了条件を満たす状態がどのような形であるかを考え、豆の座標の和が不変量であることと、豆の座標の平方和が操作ごとに2増えることを合わせるとcloseな式が得られる

335
実験してエスパーで解ける
1周するごとの状態の変化を睨むと再帰構造を見つけることができるので、それを使えば証明もできる。
2^k+1に限らず、実は一般のNでもM(N)をO(logN)で求められる

336
DFS/BFSやるだけ

337
末尾がnである数列の個数を実家DP
O(NlogN)

338

339
小さいnで実験して最適な戦略を見つける
そうするといつもの吸収マルコフ連鎖になる。遷移が特殊なので諸々の計算が簡単に済んで全体でO(n^2)
もうちょっと計算するとO(n)にもできるらしい

340
a > c なのが肝
実験。証明は帰納法

341
再帰構造があるので、再帰する。
OEISによるとG(n)はO(n^(1/φ))らしいので、2回再帰すると必要な項数がO(n^(1/φ^2))となり、十分高速

342
最大素因子の指数が満たすべき条件を考えて適当に探索。241の簡単版
空間計算量はO(√N)、時間計算量は自明にO(N)だが実際のところはよくわからない

343
最初に約分が発生するとき、割る数が何であるか考えると、最後に何になるかがわかる。
あとは因数分解すると2次式の篩 O(NlogN)。あるいはフェルマーの小定理を使ってpごとにnを列挙するほうが簡単か

344
蟻本第2版P278
数式の問題に帰着したら下から桁DPをするとARC107DになるのでO(C^2 logN)
DPの遷移を多項式乗算だとみなせてO(C^2logN)になるらしい

345
ハンガリアン法

346
nはbase n-1で11になるので3桁以上のrepunitになるbaseが存在することが必要十分。O(N^(1/3))
Goormaghtigh予想の成立を認めるならもっと早くなる。
ABC293Fの方が難しい

347
普通に篩って辞書に突っ込むとO(NlogN)
でかいところをまとめて計算しようとすると素数和を求めるやつになるのでO(N^(3/4))でできる

348
回文を列挙して全探索すればO~(ans^(5/6))

349
実験
ラングトンのアリ - Wikipedia

350
LはGの倍数なのでL=L'GとしてLの代わりにL'を全探索すると、「lcmがL'でgcdが1の個数は?」になるので解ける

続き
sugarknri.hatenablog.com

AGC063D後半

前半は自明です。後半は次の問題に帰着されます

ばかでかい正の整数Mがあります。でかすぎて値はわかりません。正の整数nを渡すとMをnで割ったあまりを返すオラクルが定数回使えます。
ax=b mod M を満たす最小の非負整数xをmで割ったあまりを求めてください。gcd(a,M)=1とします。

たぶんやってることは公式解説と同じです。こっちの方が俺には自然

以下、大文字は計算不可能な値を、小文字は計算可能な値を表すこととします。
まずオラクルを呼んでr:=M%aを求めます。Q:=floor(M/a)としてr=M-aQとなります。
a,rに対して拡張gcdをしてsa-tr=1となる非負整数s,tを求めます。r=M-aQを代入して、a(s+tQ)=1 mod Mを得ます。
a^-1 mod Mが求まったのでこれにbを掛けて、x=b(s+tQ) mod Mです。求める答えはb(s+tQ)をMで割ったあまりをmで割ったあまりです。
0<=u< aによりbt=av+uと書くと、btQ+bs=uQ+(bs-rv) mod M です。
uQ+(bs-rv)が答えなら嬉しいですね。確かめます。
uQ<=(a-1)Q<((a-1)/a)Mなので、a(bs-rv)<=M なら uQ+(bs-rv)< Mです。u>0なら同様にuQ+(bs-rv)>=0です。
u=0かつbs-rv<0のケースは簡単なので適当に処理することにすれば、uQ+(bs-rv)が答えといって良いことになります。
ということであとはQ=floor(M/a)をmで割ったあまりが分かればOKです。これはARCでやりました。
https://atcoder.jp/contests/arc111/tasks/arc111_a
おわりです。


こういうのはQとrを使ってガチャガチャやると解けがち