https://www.acmicpc.net/problem/26309
문제의 상황은 주어지는 자연수 $k$ 에 대해 다음 조건을 만족하는 서로 다른 자연수 $x$, $y$ 를 찾으라는 것입니다.
$$ \frac{2}{k} = \frac{1}{x} + \frac{1}{y} $$
만약에 이런 $x$, $y$가 존재하지 않으면 $-1$ 을 출력해야 하는데, 다행히 이런 $x$, $y$ 는 항상 존재합니다.
존재성을 확인하기 위해 식을 변형합니다.
$$ 2xy = k(x+y) $$
$$ \rightarrow (2x-k)y = kx $$
$$ \rightarrow (2x-k)2y - 2kx + k^{2} = k^{2} $$
$$ \rightarrow (2x-k)(2y-k) = k^{2} $$
이제 $x$ 와 $y$ 는 서로 다른 자연수이므로 $k^{2}$ 은 최소한 $k$ 가 아닌 다른 약수를 가져야 합니다.
그런데 $k^{2}$ 꼴의 자연수 중 1을 제외하여 약수의 개수가 제일 적은 것은 소수의 제곱입니다.
그리고 소수 $p$에 대해 $p^{2}$ 은 $p$ 를 제외한 약수를 2개 가지고 있습니다. 따라서 $x$ 와 $y$ 는 적어도 한 가지 이상 존재합니다.
문제를 풀기 위해 $k^{2}$ 의 어떤 약수 $d$ 를 가정하면
$$ x = \frac{k+d}{2} $$
$$ y = \frac{k + \frac{k^{2}}{d}}{2} $$
라고 할 수 있습니다.
이때 $x$, $y$ 는 모두 자연수이며 $x < y$ 이므로 다음을 확인할 수 있습니다.
1. $d < k$ 이다.
2. $k$ 와 $d$, $\frac{k^{2}}{d}$ 는 모두 parity 가 일치한다.
이런 조건을 만족하는 최대의 $d$ 를 구해주면 문제가 해결됩니다. 참고로, $x < y$ 에 의해 $d$ 는 자연수입니다.
그런데 $d$는 $k^{2}$ 의 약수이며, $k$는 최대 $4 \times 10^{18}$ 까지 커질 수 있는 값입니다.
이 정도 범위의 정수를 소인수분해하기 위해서는 Pollard-rho 알고리즘이 필요하겠습니다.
또한, $k^{2}$ 의 약수를 순회하는 시간이 클 수 있습니다. 공식 해설에 따르면 최악의 경우는 약 4천만개 정도라고 언급됩니다. $k$ 보다 큰 약수를 탐색하지 않는 걸로 커팅하는 게 좋습니다.
시간 복잡도는 $k$ 의 소인수분해와, $k^{2}$ 의 약수의 개수의 합으로, 대략 $O(k^{\frac{1}{4}} + k^{O(1)})$ 이 되겠습니다. 약수의 개수의 asymptotic 한 분석은 후술하겠습니다.
답이 128bit 정수 범위에서 나오므로 출력 함수를 따로 만들어야 하겠습니다. 제 코드는 다음과 같습니다.
#include <iostream>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
void print(__int128 x) {
// reference : codeforces.com/blog/entry/75044
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
template <typename Type>
class Random
{
/* implementation : https://blog.naver.com/devmachine/221240867011
*
* Type : int, long long, double
* Sample code :
* (1) Random<int> gen(-1000, 1000); // integer between -1000 and 1000
*
* (2) Random<double> gen(0.0, 1.0); // floating number between 0.0 and 1.0
*
* (3) Random<__int64> gen(0, 100000000000); // large integer between 0 and 1e11
*
* (4) Random<int> gen(-1000, 1000, 42); // Generate by user seed
*/
public:
using Distribution = typename std::conditional<std::is_floating_point_v<Type>,
std::uniform_real_distribution<Type>,
std::uniform_int_distribution<Type>>::type;
using Engine = typename std::conditional<(std::is_integral_v<Type> && sizeof(Type) > 4),
std::mt19937_64,
std::mt19937>::type;
Random(
Type min = (std::numeric_limits<Type>::min)(),
Type max = (std::numeric_limits<Type>::max)(),
typename Engine::result_type seed = std::random_device()()
)
: _engine(seed), _distribution((std::min)(min, max), (std::max)(min, max))
{
}
Type operator()()
{
return static_cast<Type>(_distribution(_engine));
}
private:
Engine _engine;
Distribution _distribution;
};
Random<long long> gen(0, 1e18, std::chrono::steady_clock::now().time_since_epoch().count());
namespace Primality {
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
bool sqrt_test (u64 N) {
/* input value : N is odd and small
* return value : {false := composite; true := prime}
* time complexity : sqrt(N)
* restriction : N < 10^9
*/
for (u32 i = 3; i * i <= N; i += 2) {
if (N % i == 0) return false;
}
return true;
}
template <bool BigInt = false>
u64 power_modular (u64 X, u64 Y, const u64 M) {
u64 result = 1;
while (Y) {
if (Y % 2) {
result = static_cast<typename std::conditional<BigInt, i128, u64>::type>(result) * X % M;
}
X = static_cast<typename std::conditional<BigInt, i128, u64>::type>(X) * X % M;
Y /= 2;
}
return result;
}
template <bool BigInt = false>
bool Miller_Rabin_Internal (u64 N, u64 K) {
/* input value : N is odd, K < N
* return value : {false := composite; true := probable-prime}
*
* explanation :
* calculate k^d, k^(2d), k^(4d), ... , k^(2^s-1 * d)
* where 2^s * d = N - 1
*
* Then, N is probably prime if k^d = +1/-1 or k^(2^k * d) = -1 mod N
*
* time complexity : O(log^2 N)
*/
u64 d = N - 1;
for (; d % 2 == 0; d /= 2) {
if (power_modular<BigInt>(K, d, N) == N - 1) {
return true;
}
}
if (u64 temp = power_modular<BigInt>(K, d, N); temp == 1 || temp == N - 1) {
return true;
}
else {
return false;
}
}
template <bool BigInt = false>
bool Miller_Rabin_test (u64 N) {
/* input value : N is odd and larger than list[i]
* return value : {false := composite; true := prime}
*
* explanation :
* Originally, Miller_Rabin_Test can be wrong by 4^-k where k is number of rounds
* But, for small N, there is a deterministic way which has 100% accuracy
*
* time complexity : O(k log^2 N)
*/
std::vector<u64> list;
if (BigInt) list = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
else list = {2, 7, 61};
for (auto& i : list) {
if (N % i == 0) return false;
if (!Miller_Rabin_Internal<BigInt>(N, i)) return false;
}
return true;
}
bool is_Prime (u64 N) {
if (N < 2) return false;
if (N == 2 || N == 3) return true;
if (N % 6 != 1 && N % 6 != 5) return false;
if (N <= 1e4) return sqrt_test(N);
if (N <= ((u64)1 << 32)) return Miller_Rabin_test(N);
return Miller_Rabin_test<true>(N);
}
}
namespace Factorize {
void Pollard_Rho_Internal (long long N, std::vector<long long>& result) {
/* result := <p1, p2, ... > where product of all elements is equal to N
* (But there can be the same elements in result vector)
*
* Caution :
* (1) include <algorithm>, <vector>, <numeric>, <cstdlib>, <random>, <chrono>
* (2) for u64 or larger types, implement your own gcd and abs
* (3) for i64 or larger types, miller-rabin should be safe "enough"
* (especially for multiplication)
*
* time complexity : approximately O(n^(1/4)), but actual proof is still open
*
* implementation : https://blog.naver.com/PostView.naver?blogId=jinhan814&logNo=222141831551
*/
if (N == 1) return;
if (Primality::is_Prime(N)) {
result.push_back(N);
return;
}
if (N % 2 == 0) {
result.push_back(2);
Pollard_Rho_Internal(N / 2, result);
return;
}
// cycle-detection on functional graph (hare and tortoise)
long long A = 0, B = 0, C = 0, G = N;
do{
auto f = [&](long long X) -> long long {
return ((__int128)X * X + C) % N;
};
if (G == N) {
A = B = gen() % (N - 2) + 2;
C = gen() % 20 + 1;
}
A = f(A);
B = f(f(B));
G = std::gcd(std::abs(A - B), N);
}while (G == 1);
Pollard_Rho_Internal(G, result);
Pollard_Rho_Internal(N / G, result);
}
std::vector<long long> Pollard_Rho (long long N) {
std::vector<long long> result;
Pollard_Rho_Internal(N, result);
std::sort(result.begin(), result.end());
return result;
}
std::vector<std::pair<long long, long long>> Multiplicity (long long n) {
auto pF = Pollard_Rho(n);
std::vector<long long> uPF;
uPF.assign(pF.begin(), pF.end());
uPF.erase(unique(uPF.begin(), uPF.end()), uPF.end());
std::vector<std::pair<long long, long long>> result;
for (auto& i : uPF) {
result.push_back(std::make_pair(i,
upper_bound(pF.begin(), pF.end(), i) -
lower_bound(pF.begin(), pF.end(), i))); // prime number and its multiplicity
}
return result;
}
}
using namespace std;
int main() {
long long k;
cin >> k;
auto temp = Factorize::Multiplicity(k);
for (auto& i : temp) {
i.second *= 2;
}
auto exp = [](__int128 x, long long y) -> __int128 {
__int128 result = 1;
while(y--) result *= x;
return result;
};
long long D = 1;
std::function<void(int, int, long long, __int128)> Internal = [&](int pos, int last, long long power, __int128 cur) -> void {
cur *= exp(temp[pos].first, power);
if (cur >= k) return;
if (pos == last) {
if (D < cur) {
// divisor of k^2, less than k, larger than current value D
if (k % 2 == cur % 2) {
if (((__int128)k * k / cur) % 2 == k % 2) {
D = cur;
}
}
}
}
else
for (long long i = 0; i <= temp[pos + 1].second; i++) {
Internal(pos + 1, last, i, cur);
}
};
for (long long i = 0; i <= temp[0].second; i++) Internal(0, temp.size() - 1, i, 1);
__int128 y = (__int128)k * k / D;
y = (y + k) / 2;
__int128 x = ((__int128)k + D) / 2;
assert((__int128)k * k == (2 * x - k) * (2 * y - k));
print(x);
std::cout << ' ';
print(y);
return 0;
}
(C++20, 532ms, 2036KB, 제출번호 69669250)
약수의 개수에 관한 글들을 읽어보았는데, math.stackexchange.com 의 글이 좋은 것 같습니다.
OEIS 에서 highly composite numbers 를 찾아보니, $k$ 가 다음 값으로 주어질 때
$$ k = 3066842656354276800 = 2^{6} \times 3^{3} \times 5^{2} \times 7^{2} \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31 \times 37 \times 41 $$
$k^{2}$의 약수의 개수가 44778825 개가 나옵니다. 아마 공식 해설은 이걸 언급한 것 같습니다.