Floor and Mod
rating : 1700
tags : binary search , brute force, math , number theory

문제

한 쌍의 양수 (a,b)에 대해서, a/b(floor:나머지를 버리고 몫만 취하는 연산)==a%b(modular)이면 (a,b)쌍을 특별하다고 정의합니다. 1≤a≤x and 1≤b≤y인 x,y가 주어질 때 이러한 특별한 쌍이 몇개가 있는지 찾는 것이 문제입니다.

접근

처음에 풀 때 a<b , b<=a<2b , 2b<=a<3b ... 이런 식으로 접근해서 규칙을 찾으려고 했습니다. a,b의 제한 조건도 따져줬습니다. 생각이 너무 복잡해졌습니다. 결국 설계를 포기하게 됩니다.

어려움

큰 제한

x , y (1≤x,y≤10억) 이어서 단순한 브루트포스로는 풀 수 없겠다는 것을 알게 됩니다. 선택할 수 있는 솔루션의 폭이 좁아져서 압박감을 느낍니다. 그리고 모든 케이스를 합친 제한이 10억이 아니라 각 테스트 케이스 마다 10억씩 수가 들어오게 되므로 적어도 n보다는 작은 sqrt(n),log(n) 정도의 시간복잡도로 풀어야했습니다. 막막해집니다.

수식

a/b==a%b인 (a,b) 쌍을 찾아라.

단순한 수식입니다. 그런데 평소에 나머지나 몫이나 나눈 몫과 나머지가 같은 수에 대해서 생각을 잘 안 하니 이 수식이 어렵게 보였습니다. 내가 모르는 뭔가 있을거 같은 느낌입니다. 이 수식을 활용해야 한다는 사실이 어려운걸지도..?

해결

a/b == a%b ==k

위 수식에서 ==k로 놓고 풀어볼 생각을 못했습니다. 사실 그런 생각을 했다는건 어느정도 설계가 됐고 갈피를 잡았다는 의미일 것입니다. '==k' 3글자를 종이에 쓰기 힘든 이유입니다.
어쨌든 이렇게 두고 a를 표현해 봅니다.

a=b*k+k

k는 a를 b로 나눈 몫이자 나머지입니다. 따라서 b>k입니다. 이를 이용해서 부등식을 세울 수 있습니다. k의 범위가 x의 제곱근이하로 줄어듭니다.

kk <kb+k =a <=x
=> k<=sqrt(x)

이제 각 고정된 k에 대해서 b의 범위를 구해줍니다. b와 k에 따라 a는 유일하게 결정되므로 b의 범위만 세아리면 됩니다.
b의 제한 조건은 아래 3가지입니다.
1. k < b
2. 1<=b<=y
3. a=kb+k에 의해 1<=kb+k<=x

종합한 b의 범위는 아래와 같습니다.

k+1<= b <= min(y,(x-k)/k)

모든 범위의 k에 대해 다 더해주면 답이됩니다.

피드백

정수론

정수론 문제는 틀릴만 했습니다. 식 전개하는 부분이 만만치는 않았습니다. 그렇다고 못할 정도도 아니었는데, 몇 문제 더 풀어보면 감이 잡힐거 같습니다.

시간복잡도

시간복잡도를 줄여야 한다는 생각은 들었습니다. 주어진 식의 조건을 따져서 범위를 줄이는 아이디어는 꽤 많이 쓰이는데 수식으로 접근할 생각 자체를 못했습니다. 이 문제는 꽤 신선하게 시간복잡도를 줄이는 문제였던거 같습니다.

말 그대로 뇌정지가 와서 생각을 전개시키기를 포기했습니다.
생각을 전개하는 힘 자체가 약했던 것이 못풀은 근본 원인입니다.

using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int tc; cin>>tc;
	while(tc--){
		int x,y; cin>>x>>y;
		// a/b = a%b =k
		// => a=b*k+k
		
		int maxk=(int)sqrt(x);
		ll cnt=0;
		for(int k=1;k<=maxk;k++){
			int maxb=min((x-k)/k,y);
			int minb=k+1;
			int add=maxb-minb+1;
			if(add>0) cnt+=add;
		}
		cout<<cnt<<"\n";
	}
}