C - チップ・ストーリー ～白銀編～
解法
要は全てが掛け合わされるので、max(p) * max(q) <= N なら良い
排反に数えるには、pの最大値がpmの場合のpの組み合わせと、条件を満たすqの組み合わせというのを掛けていけばいい
pの最大値がpmになる組み合わせは、pm^10-(pm-1)^10で求められる
Submission #3679873 - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選
signed main() {
cin >> N;
mint res = 0;
for (int pm = 1; pm <= N; ++pm) {
mint pc = mpow(pm, 10) - mpow(pm - 1, 10);
mint qc = mpow(N / pm, 10);
res += pc * qc;
}
cout << res << endl;
return 0;
}
