DIVERTA2019_D - DivRem Number

[zeikar]

Problem link

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

Problem Summary

주어진 N에 대해 나눈 몫과 나머지가 같도록 하는 m을 모두 구해 더하면 된다.

Solution

수식을 조금 이용하면 된다.
먼저 구하고자 하는 favorite number를 m으로 두면

x = N / m = N % m

이 성립해야 되고, 양쪽으로 식을 정리하면

N = m * x + x
m = (N - x) / x

이 된다.

단, 1부터 모든 n까지 탐색은 시간 초과가 되므로 sqrt(n) 까지만 돌려주면 된다.

Source Code

#include <iostream>
using namespace std;

int main() {
	long long n;
	cin >> n;

	long long ans = 0;

	for (long long x = 1; x * x <= n; x++)
	{
		long long m = (n - x) / x;

		if (m == 0)
		{
			continue;
		}

		if (n / m == n % m)
		{
			ans += m;
		}
	}

	cout << ans << endl;
}