ARC091 D : Remainder Reminder(400)

作成日:2018.03.14
最終更新日:2018.03.14

問題概要

問題本文

 $N$以下の正整数の組$(a,b)$で、$a$を$b$で割った余りが$K$以上であるようなものの数を求めよ。
制約
$1 \leq N \leq 10^5$
$0 \leq K \leq N-1$

考え方

 除算を表す式$a=bq+r$$(0 \leq r \lt b)$において$r \geq K$であるものの数を求めれば良い。 $K=0$の時はすべての組が条件を満たし答えは$N^2$であることは明らかであるから、以下では$K \geq 1$であるとする。 また$K \leq r \lt b$であるから、以下では$b$は$K+1$以上であるとして考える。 $a$を$1$から増やしていくと$r$は$1,2,...,b-1,0,1,...$と周期的に変化する。 そこで$b$を固定して考えると、条件を満たす$a$が$b(q+1) \leq N$である$q$ごとに$((b-1)-K+1)$個、$bq \leq N \lt b(q+1)$を満たす$q$においては$max(0,N\%b-K+1)$個あることが分かる。 $b$は$O(N)$種類なので、$b$の値ごとに考えることで十分高速に答えを求めることができる。

ソースコード

マクロ等はこちら

LL N,K;
LL ans;

int main(){
	cin >> N >> K;
	if(K == 0) return cout << N*N << endl , 0;
	repp(b,K+1,N+1){
		ans += N/b * (b-K);
		ans += max((LL)0,N%b-K+1);
	}
	cout << ans << endl;
	return 0;
}

解法まとめ

 $K=0$の時は$N^2$が答えである。(6行)
 そうでない時、$K+1 \leq b \leq N$を満たす$b$それぞれについて$[N/b](b-K)$と$max(0,N\%b-K+1)$を加えたものが答えである。(7-11行)

ARC091の他の問題 C E F

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら