ABC097 C - K-th Substring

問題概要:
文字列 $s$ が与えられる。 $s$ の部分文字列のうち、辞書順で $K$ 番目に小さいものを出力せよ。
（ $|s| \leq 5000$ ）

※ $N = |s|$ とします
基本方針としては、制約が小さいのでC++ならsetにでも突っ込んで順番に取り出せばよいです。setはデフォルトでソートされた状態で保持してくれますからね。

というわけで一番最初に提出したコードがこちら。

Submission #11947075 - AtCoder Beginner Contest 097

うん、ループは $O(N ^ 2)$ だしsetへのinsertは対数オーダーだから通るはず……って言ってると、なぜかTLEに。さて、なぜでしょうか。

強い人に質問してみると、これ実は $O(N ^ 3 \log N)$ になってるらしいとのこと。

どこで $O(N)$ が発生しているかというと、文字列の比較でした。
文字列の比較なんてどこでした？という感じなのですが、よく考えてみるとsetへinsertするときに毎回発生しています。ソートされた状態で要素を保持するためには比較をしなければなりませんからね……。これが盲点でした。
ソートをする際、比較そのものの回数は $O(\log N)$ なわけですが、その比較1回あたりに $O(N)$ かかっていたわけです。（正確には比較する文字列の長さのmin？）

そんなわけで、もうちょい計算量を削らなければなりませんが、この問題の場合には $K$ の制約が小さいおかげで、長さ6以上の部分文字列はsetへinsertしないことによりTLEを回避できました。

ACコード（1行追加しただけ）:
Submission #11947828 - AtCoder Beginner Contest 097

ABC162 E - Sum of gcd of Tuples (Hard)

問題概要:
$1$ 以上 $K$ 以下の整数からなる長さ $N$ の数列の全てについてgcdを求め、その和を計算せよ。
（ $2 \leq N \leq 10 ^ 5, 1 \leq K \leq 10 ^ 5$ ）

基本方針は公式解説の通りで、 $1 \leq X \leq K$ に対して最大公約数が $X$ となるような数列の数を求めてその和を求めます。

こちらが書いたコード。
Submission #11975132 - AtCoder Beginner Contest 162

注目してほしいのは、もちろんループの部分。

for (int x = k; x > 0; x--) {
    lint t = k / x;
    t = modpow(t, n);
    lint x2 = x + x;
    while (x2 <= k) {
        t -= c[x2];
        x2 += x;
    }
    t = ((t % MOD) + MOD) % MOD;
    c[x] = t;
    res += t * x;
    res %= MOD;
}

内側のwhileで、倍数の分の数を引いています。
ここで気になるのが、このwhileループ、計算量はどうなるの？ということです。 ACを出したときはよく分かっていないまま通ってしまったのですが、別にTLEとなってもおかしくなかったと思います。
ここで今一度、ループの実行回数を考えてみます。

whileループの回数は、コード中の変数 $x$ の値に依存しています。具体的には、 $x$ の倍数の個数の分だけ、ループが実行されるはずです。