백준 14256번, SSR 풀이

문제

백준 14256번

풀이

$ SSR(A, B) = (\sqrt{A} + \sqrt{B}) ^ 2 $이 정수가 되어야 합니다. 식 정리를 해봅시다.

$$ = A + B + 2 \cdot \sqrt{AB} $$

$A, B$는 이미 정수이므로, $ \sqrt{AB} $가 정수가 되면 됩니다.

 

따라서, $ AB $가 제곱수가 되면 됩니다.

 

이제, $ AB $가 제곱수가 되는 경우의 수를 모두 구하면 됩니다.

 

$ A $를 고정시키고, 가능한 $ B $의 개수를 세봅시다.

$ A $를 소인수 분해한 뒤, 지수가 홀수인 밑만 곱해준 수를 $ c $라고 정의합니다.

그러면, $ B $는 $ c \cdot k ^ 2 $이라고 둘 수 있습니다. ($k$는 임의의 정수)

(왜냐하면, $B$가 항상 $c$의 배수여야 $ c^2 \cdot k^2 $이라는 제곱수꼴이 되기 때문입니다.$)

 

예를 들어봅시다. $2$를 소인수분해하여 구한 $c = 2$입니다.

$AB$가 제곱수가 되려면, $B$가 무조건 $2$를 포함하고 있어야 합니다. ($c$의 배수)

 

위 조건에서 아래와 같은 부등식을 세울 수 있습니다.

$$ c \leq B \leq M (B = c \cdot k ^ 2)$$

따라서,

$$ 1 \leq k^2 \leq \frac{M}{c} $$

$$ 1 \leq k \leq \sqrt{\frac{M}{c}} $$

라는 식을 세울 수 있으므로, $A$가 정해지면 가능한 $k$(또는 $B$)의 개수는 $ \sqrt{\frac{M}{c}} $입니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef unordered_map<int, int> mpii;

int vis[280];
vi prime;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	for (int i = 2; i <= 279; i++) {
		if (vis[i]) continue;
		prime.emplace_back(i);
		for (int j = i; j <= 279; j += i) vis[j] = 1;
	}

	auto extract = [](int a) {
		int ret = 1;
		for (const auto &p : prime) {
			if (!a) break;
			int cnt = 0;
			while (a && a % p == 0) a /= p, ++cnt;
			if (cnt % 2) ret *= p;
		}
		if (a) ret *= a;
		return ret;
	};

	int n, m; cin >> n >> m;
	int ans = 0;
	for (int i = 1; i <= n; i++) ans += sqrt(m / extract(i));
	cout << ans;
}