ARC_091_B / ABC_090_D - Remainder Reminder

[zeikar]

Problem link

https://atcoder.jp/contests/arc091/tasks/arc091_b

Problem Summary

N을 넘지 않는 a, b 쌍 중에서 a % b가 K 보다 크거나 같은 개수를 구하는 문제.

Solution

예제 1에 힌트가 있는데, b에 대해 K + 1부터 N까지 다 돌려가면서 나머지가 K 이상이 되는 a의 개수를 구해주면 된다.

N % b를 r로 두면, a가 r 이하인 경우엔 N / b + 1번 가능하고 r보다 큰 경우는 N / b번만 가능하다.

K == 0일 땐, a == 0인 경우를 처리하기 위해 결과에서 N을 빼주면 된다. (문제에서 positive integers 라고 했으므로)

Source Code

#include <iostream>
using namespace std;

int main() {
	int n, k;

	cin >> n >> k;

	long long res = 0;
	for (int b = k + 1; b <= n; b++)
	{
		// k to b-1
		int cnt = b - k;
		res += cnt * (n / b);

		res += max(0, n % b - k + 1);
	}

	if (k == 0)
	{
		res -= n;
	}

	cout << res << endl;
}