diverta 2019 D - DivRem Number(500)

D - DivRem Number

概要

整数Nが与えられる。このときN以下の整数mで、Nを割った時の商とあまりが等しいものはいくつあるか。

制約

1 ≦ N ≦ 10^12

方針

N以下のすべての整数を試すことはできない。
Nをxで割った時の商をr、あまりをqとすると、N = rx + qと書ける。r = qであればN = r(x+1)である。
よって商とあまりが等しいxは(Nの約数-1)の形で書けるため、実際にNの約数-1を全探索すればよい。
Nの約数は（平方根以外は）d, N / d のペアになっているため、その片方を走査するだけでよくO(N^(1/2))の計算量で間に合う。

解答

Submission #5372044 - diverta 2019 Programming Contest

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N;
	cin >> N;
 
	if(N == 1){
		cout << 0 << endl;
		return 0;
	}
 
	if(N == 2){
		cout << 0 << endl;
		return 0;
	}
 
	ll ans = 0;
	for(ll d = 1; d * d <= N; d++){
		if(N % d > 0) continue;
 
		ll x = d-1;
		if(x > 0 && N / x == N % x) ans += x;
 
		if(d * d == N) continue;
		ll y = N / d - 1;
		if(y > 0 && N / y == N % y) ans += y;
	}
 
	cout << ans << endl;
}