[ boj : 14256 ] SSR

www.acmicpc.net/problem/14256

14256번: SSR

문제 : SSR(A, B) = (sqrt(A) + sqrt(B))^2 이라고 하고 1<=A<=N , 1<=B<=M 일때 정수가 되기 위한 A,B이 될 수 있는 쌍의 개수를 구하시오.

 

해설 : 일단 저 식을 전개를 합니다.

그럼 A+B+2sqrt(AB) 가 됩니다. 그럼 결국 AB가 어떤 수 (x)의 제곱수가 되면 정수가 되겠죠.

그럼 전부다 해보면 됩니다....가 아니라 이렇게 하면 아마 tle가 뜰겁니다.

 

A 를 먼저 소인수 분해 합니다. 그럼 각 소수들의 집합들이 나올 것 입니다.

그 중에 각 소수들의 횟수가 홀수번 나온 수도 있을 것이고 짝수번 나온 수들도 존재하겠죠.

그러나 우린 짝수번 나온 소수들에는 관심이 없습니다. 그 이유는 짝수번 나온 소수들은 이미 x^2 꼴이니 이 수들은 루트를 벗어나 정수형이 되기 때문이죠.

 

그럼 홀수번나온 이 소수들을 루트 밖으로 벗어나게끔 해주어야 되는데 만약 B에 이 소수들의 집합이 그대로 포함되어있다면??그럼 A와 B를 곱하면 전부 짝수번 횟수가 되는거여서 루트 밖으로 벗어날 수 있게 됩니다.

 

즉, A를 소인수분해 해서 홀수번 나온 소수들을 전부 곱한것을 B가 가지고 있어야 된다는 뜻입니다. 이 홀수번 곱한 값들을 p 라고 하겠습니다.

그럼 B = p * x^2 꼴이 되어야지만 sqrt(AB)가 정수가 될 수 있겠죠.

 

p<=B<=m 이니 p<=p*x^2 <=m 으로 치환할 수 있으며 이것을 각각 정리하면

1 <= x^2 <=M/p

1 <= x <= sqrt(M/p)

 

즉,각 수에 대하여 sqrt(M/p)의 개수만큼 존재합니다. 이를 전부 더해주면 답이 되겠죠.

#include<bits/stdc++.h>

using namespace std;

int n, m;
int div(int x);

int main()
{
	int ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x = div(i);
		ans += (int)sqrt(m / x);
	}
	cout << ans;
	return 0;
}
int div(int x)
{
	int ret = 1;
	for (int i = 2; i * i <= x; i++) {
		int cnt = 0;
		while (x % i == 0) {
			cnt++;
			x /= i;
		}
		if (cnt & 1)
			ret *= i;
	}
 	return ret*x;
}