チップ・ストーリー ～白銀編～ [DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 C]

https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c

解説

https://beta.atcoder.jp/contests/ddcc2019-qual/submissions/3650243

条件を整理しよう

• 数列の値は全て自然数
• 各チップ(i,j)にP[i]*Q[j]
• 各チップの値は1以上N以下

2,3番目の条件を見ると、最終的には「Pの最大値*Qの最大値≦N」が満たされればいいとわかる。
なので、最大値に注目した数え上げをしよう。
　
最大値がxとなるような組み合わせはx^10かなと思う所だが、これでは最大値がx以下の組み合わせも含まれる。
ika[x] := x^10
これを使うと、最大値がちょうどxであるのは、(最大値がx以下) - (最大値がx-1以下)である。
just[x] := ika[x] - ika[x-1]
　
答えの数え上げは、Pの最大値を全探索すれば、独立に数え上げられるので、それでやる。
Pの最大値がiならば、Qの最大値はN/i以下である必要がある。
よって、just[i]*ika[N/i]の総和が答え。

int N;
mint ika[101010], just[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
 
    rep(i, 1, N + 1) ika[i] = mint(i) ^ 10;
    rep(i, 1, N + 1) just[i] = ika[i] - ika[i - 1];
 
    mint ans = 0;
    rep(i, 1, N + 1) ans += just[i] * ika[N/i];
    cout << ans << endl;
}