[백준 28138번] 재밌는 나머지 연산 (C++)

문제링크 : https://www.acmicpc.net/problem/28138

28138번: 재밌는 나머지 연산

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    ll N, R, result = 0;
    cin >> N >> R;

    ll tmp = N-R;
    for(ll i=1; i<=sqrt(tmp); i++)
    {
        if(tmp%i==0) 
        {
            if(i>R) result+=i; //전반부 약수
            if(i*i!=tmp && tmp/i>R)result+=tmp/i; //중복방지 및 후반부 약수
        }
    }
    cout << result;

    return 0;
}

나머지 공식을 보면 N = mx + R 이다.

이를 수정하면 N-R = mx -> (N-R)/x = m이다.

즉 (N-R)이 나누어떨어져야하므로 (N-R)의 약수를 구해주면 된다.

 

(N-R)에 루트를 씌워주고 반복문을 돌리면서 약수를 확인한다. (전반부 약수 확인)

이때 나머지가 R보다 커야하므로 현재 i의 값이 R보다 커야만 한다.

 

또 해당 i가 약수라면 tmp/i도 체크해준다 (후반부 약수 확인)

이때 i*i!=tmp라는 조건을 넣었는데 이는 중복방지를 위함이다. 

해당 조건을 넣지 않으면 위에서 이미 i*i에 대해 탐색을해서 중복값이 들어가게 된다.

 

N의 범위가 매우 크므로 O(N)으로 풀면 시간초과가 발생한다

그래서 O(sqrt(N))으로 풀어야 하는 문제다.