問題文はこちら(Problem - D - Codeforces)まず\( (x^y)^z = (x^z)^y \)であることから\(a_4, a_8, a_{12}\)が候補から外れる。 単純に与えられた式を計算するとオーバーフローしてしまうため、対数をとって比較していく。ただし、\(x (i) x,y,zが全て1より…

sourceとsinkを追加し流量制限にa[i],b[i]を与えることで二部グラフのフローになることは本番中に気づいたが、YESだった場合に経路復元する方法が分からなかった。考えてみると、逆辺のcapはその辺に流したフローの量であるから、ここから容易に復元すること…

dp[i]をi以下の各自然数について素因数分解したときの素因数の個数の総和とすると、dp[a]-dp[b]が答えとなる。よって、前処理で素因数分解をしておけばいい。エラトステネスの篩をするときにsieve[i]にiの素因数のひとつ(最小や最大のものに固定することもで…