parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 整数 問題1<=a,b<=Na mod b >= K組(a, b)としてありうるものを数えよ1<=N<=10^5 解説0<=K<b, q>=0r >= Ka = bq + rr = a-bqK<=r<bK<=a-bq<bK+bq<=a<b(q+1)よって1<=b<=Nの範囲でbを総当たりして更にK+bq<=N の範囲でqを総当たりこれは調和数を考えると実行時間がO(NlogN)になるやつオーバーフローに注意 Submission #2204827 - AtCoder Regular Contest 091 調和数 (発散列) - Wikipedia 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2018%2F03%2F14%2F205635" title="D. Remainder Reminder | AtCoder Regular Contest 091 - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-03-14 20:56:35 rich https://par.hateblo.jp/entry/2018/03/14/205635 1.0 100%