これの続き
sugarknri.hatenablog.com
51
3の倍数で枝刈り
52
有名問題すぎる
53
尺取
rが小さいうちは境界を直接計算すると早い
54
気合
55
多倍長整数
56
多倍長整数
嘘下界を使って嘘枝刈りで高速化
57
連分数の最後に1項増やしたときの挙動を知っていますか
分子と分母の一般項を求めると、N→無限での比率の極限がlog10(2)/2だと予想できる。面白いね
58
一般項が二次多項式で与えられる数列を篩にかける方法を知っていますか
あとこれ
上限が不明なときの問題解決法 - inamori’s diary
59
頻度分析を知っていますか
60
全探索
5-cliqueを求める問題だと思ってNetworkXにぶち込んでも解けるそうです（え？）
61
全探索
条件が厳しいところからやる
62
49と同じ
ちなみに「5個」ではなく「7個」に対する答えは10314675896832ではありません。問題文を正しく読めましたか？
63
高校数学
常用対数表を見ながら紙とペンで解け
64
分母の有理化
実はN=4k,4k+3のときには必ず偶数周期になることが証明できます。ヒント：ペル方程式
65
57と同じ
分母のなす数列はp-recursiveなので、高速に求めることもできます
66
ペル方程式の解き方を知っていますか？
64,65で書いたコードが役に立ちます
実は賢くやると多倍長整数なしでも解けます。マジ？
めちゃくちゃやばい制約でも解けます。マジ？？？？？
SPOJ.com - Problem PELLFOUR
67
18で解説した
68
手で解け
69
トーティエント関数の性質を知っていますか
手で解け
70
正解者掲示板が嘘解法だらけ。何が嘘か考えて1つずつ論破しましょう
実はプラキューを(ダイクストラのように)適切に使うと、嘘なしで、余分な計算をかなり少なくしてn/phi(n)の順にnを取り出すことができます
類題は615です
71
ファレイ数列を知っていますか
近似したい分数をa/bとして、O(N)やO(b)やO(log b)の解法があります
72
お ま た せ い つ も の 親 の 顔 よ り 見 た totient sum
https://yukicoder.me/wiki/sum_totient
73
bounded totient sum、実は72と同じ計算量で解けます（えー）
74
競プロでありがち。実装が面倒
並び替えを同一視して状態を圧縮もできる
75
39で挙げた生成行列のやつでまず互いに素なものを生成したあと約数ゼータ変換
O(NlogN)
76
DPでO(N^2)
五角数定理でO(N^1.5)
五角数定理＋FPSの逆数でO(NlogN)
77
DPでO(N^2/logN)
FPSのlog+expでO(NlogN)
78
76でやった
79
トポロジカルソートして解けるならそれで終わり
一般の場合はハルヒ問題(最小超置換問題)の一般化なのでヤバそう
80
開平法を知っていますか
むしろ知らなければisqrt(D*10**198)で解けます
81
DP O(N^2)
82
愚直DP O(N^3)
賢いDP O(N^2)
83
ダイクストラ O(N^2 logN)
84
モンテカルロ
85
手で解け
86
またピタゴラス数の列挙です
87
全探索
条件が厳しいところからやる
88
DFS
89
実は数種類の置換をするだけで十分です
90
全探索
91
全探索 O(N^4)
少し考えるとO(N^2 logN)
gcdを表引きするとlogが落ちる
92
メモ化再帰でO(N)
桁DPと組み合わせるとO((logN)^2)
93
全探索
94
ペル方程式
95
74でやった
96
naked single＋バックトラックだけで解ける
比較的簡単な理詰めだけで解けるので、ひとによっては手で解いた方が早いかも
97
二分累乗
オイラーの定理
98
全探索
条件が厳しい方からみる 条件が厳しいのはどーっちだ？
99
高校数学
なお一般には破滅します
No.219 巨大数の概算 - yukicoder
100
ペル方程式
