https://www.acmicpc.net/problem/5647
5647번: 연속 합
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, q값이 주어진다. q는 1014보다 작은 양의 정수이다. 입력의 마지막 줄에는 0이 하나 주어지고, 입력
www.acmicpc.net
간단한 모델링을 해보면, 정수 $x$부터 $p$개 정수의 합은 다음과 같습니다.
$$ x + (x+1) + \cdots + (x+p-1) = \frac{p(2x+p-1)}{2} $$
문제의 서술을 그대로 따라가면, 이는 $x+p$부터 $q$개 정수의 합과 같아야 하며 다음 식으로 이어집니다.
$$ \frac{p(2x+p-1)}{2} = \frac{q(2x+2p+q-1)}{2} $$
아무 고민도 없이 의식의 흐름대로 쓴 식 같지만, 이대로 풀어도 풀린다는 것이 이 문제의 신기한 점 같습니다.
문제의 조건을 만족하기 위해 위 방정식은 정수 해를 가져야 합니다. 즉
$$ x = \frac{-p^{2}+p(2q+1)+q(q-1)}{2(p-q)} \in \mathbb{Z} $$
이때 $p > q$ 라는 것은 직관적으로 나오기도 하고, 위 $x$에 대한 식으로부터 얻을 수도 있겠습니다.
식을 통해 얻는다는 것은, 문제의 $q$개의 양의 정수의 합이라는 조건을 사용하는 것입니다.
$p$가 $q$보다 작게 되면, 그때 $x+p < 0$ 이므로 문제의 조건과 어긋납니다. 따라서 $p > q$ 여야 합니다.
추가로 $p > q$일 때 $q^{2} \geq x \geq \frac{-p}{2}$ 이고, 자연스럽게 $x+p$ 부터의 $q$개 정수는 양의 정수가 될 수밖에 없습니다.
그러면, $q$가 주어졌을 때 $p$를 얻으려면 정말 나눗셈을 계속 반복하는 방법밖에 없을까요? 당연히 문제를 풀려면 일반화를 해야하는데, 예제를 해석하면서 일반화의 단서를 찾아보겠습니다.
Small Example
$q=5$ 일 때, $p=6$부터 반복해서 나눗셈을 수행합니다. 결과적으로 $x$가 정수인 $p$ 값은
$$ p=6,7,10,15,30,55 $$
으로 총 6개가 나오게 됩니다. 그런데 이 각각의 $p$ 값에 대해 $p-q$ 을 구해보면...
$$ p=6,7,10,15,30,55 $$
$$ \rightarrow p-q=1,2,5,10,25,50 \;\; (q=5) $$
뭔가 $p-q$가 50의 약수로 나타나는 것 같습니다.
마찬가지로 $q=3$일 때 $x$가 정수인 $p-q$를 구해보면
$$ p-q=1,2,3,6,9,18 \;\; (q=3)$$
뭔가 18의 약수로 나타나는 것 같습니다.
Coarse Conjecture
여기서 추측할 수 있는데, 편의를 위해 $p = q+k$ 라고 놓으면
$$ k | 2q^{2} \rightarrow x \in \mathbb{Z} $$
이제 제대로 된 식 변형을 통해 추측이 맞는지 틀린지 검증해보겠습니다.
Counter Example : q=2, q=4
$p = q + k$를 도입하여 식을 간략하게 바꾸면
$$ x = \frac{2q^{2}+k-k^{2}}{2k} \in \mathbb{Z} $$
을 얻습니다.
간단하게 $q=2,4$를 넣어보면 앞선 추측은 짝수 $q$에 대해 틀렸다는 걸 알 수 있습니다.
참고로, $q=2$ 일 때는 $k = 1,8$, 그리고 $q=4$일 때는 $k=1,32$ 입니다.
하지만, 홀수 $q$에 대해서는 확실하게 추측이 옳음을 증명할 수 있습니다.
Answer for odd q
$x$에 대한 식을 한 번 더 변형하면
$$ x = \frac{q^{2}}{k} + \frac{1}{2} + \frac{-k}{2} \in \mathbb{Z} $$
가 됩니다. 여기서 $q$가 홀수라면 적어도 $k | q^{2}$ 인 모든 $k$는 $x$를 정수로 만들어줍니다.
그러면, $k = 2q^{2}$ 일 경우만 성립하면 되는데, 이는 쉽게 $x = -q^{2} + 1$ 로써 참임을 알 수 있습니다.
마지막으로, $k > 2q^{2}$ 일 때 $x$가 정수가 되는 예가 있는지 살펴보면 홀수 $q$에 대한 답을 얻게 됩니다.
그런 $k$는 역시 없으므로, $q$가 홀수일 때에 대한 최종적인 답은 $2q^{2}$ 의 약수의 개수입니다.
Answer for even q
$q=2,4$ 의 경우를 생각하면, 잘못된 결론에 빠지기 쉽습니다. 여기서는 $q=6$ 을 계산해보겠습니다.
$$q=6 \rightarrow k = 1,3,9,\cdots$$
결론적으로 짝수 $q$에 대해 홀수 $a$ 가 $q=2^{n} \times a$ 로 표현되는 수라면,
$$ x = 2^{2n} \times \frac{a^{2}}{k} + \frac{1}{2} + \frac{-k}{2} \in \mathbb{Z} $$
가 되고, 이로부터 $k$는 $a^{2}$ 의 약수이면 충분하다는 걸 알게 되었습니다.... 그게 끝일까요?
여기까지의 결론을 제출하면 25%에서 틀리게 됩니다. 놓친 예시가 뭐냐면,
$$ q = 14 \rightarrow 2^{2} \times \frac{49}{8} + \frac{1}{2} + \frac{-8}{2} = 21 \in \mathbb{Z} $$
와 같은 경우입니다.
이제 $k = 2^{2n+1} \times \frac{a^{2}}{d}$ 를 대입해보면, (단 $d$는 $a^{2}$ 의 약수)
$$ x = \frac{d}{2} + \frac{1-k}{2} \in \mathbb{Z} $$
임을 알 수 있습니다.
따라서, 짝수 $q$에 대한 최종적인 답은 $a^{2}$ 의 약수의 개수의 2배입니다.
Final Result
이제 위 결론을 그대로 구현하면 AC를 받을 수 있지만, exploit하자면
어차피 $2q^{2}$ 의 약수의 개수나, $q^{2}$ 의 약수의 개수에 2를 곱한 것은 서로 같습니다.
따라서 인풋에서 2를 걷어낸 뒤, 이 글의 표현에 따르면 $a$ 또는 $q$에 대해,
$a^{2}$ 또는 $q^{2}$ 의 약수의 개수를 알아낸 뒤 2배 해주면 충분합니다.
$q \leq 10^{14}$ 인데, c++ 기준 sieve로도 충분히 빠르게 돌아가긴 합니다. 하지만 Pollard-rho, Miller-Rabin을 쓰는 게 더 빠르긴 합니다.
제 코드는 다음과 같습니다.
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <chrono>
#include <random>
#include <vector>
namespace Primality {
using u32 = unsigned int;
using u64 = unsigned long long;
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;
}
u64 power_modular (u64 X, u64 Y, u64 M) {
u64 result = 1;
while (Y) {
if (Y % 2) {
result = result * X % M;
}
X = X * X % M;
Y /= 2;
}
return result;
}
using i128 = __int128;
u64 power_modular_safe (u64 X, u64 Y, u64 M) {
u64 result = 1;
while (Y) {
if (Y % 2) {
result = (i128)result * X % M;
}
X = (i128)X * X % M;
Y /= 2;
}
return result;
}
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_safe(K, d, N) == N - 1) {
return true;
}
}
if (u64 temp = power_modular_safe(K, d, N); temp == 1 || temp == N - 1) {
return true;
}
else {
return false;
}
}
bool Miller_Rabin_test (u64 N) {
/* input value : N is odd and large
* 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 = {2, 7, 61};
if (N > ((u64)1 << 32)) list = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (auto i : list) {
if (N % i == 0) return false;
if (!Miller_Rabin_Internal(N, i)) return false;
}
return true;
}
bool is_Prime (u64 N) {
if (N < 2) return false;
if (N == 2 || N == 3 || N == 7 || N == 61) return true;
if (N % 6 != 1 && N % 6 != 5) return false;
if (N <= 1e2) return sqrt_test(N);
return Miller_Rabin_test(N);
}
}
template <typename Type>
class Random
{
/* implementation : https://blog.naver.com/devmachine/221240867011
*
* include <chrono> and <random>
*
* 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 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>, <numeric>, <cstdlib>, <random>, <chrono>, <vector>
* (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;
}
}
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
while(1) {
long long X;
cin >> X;
if (X == 0) break;
if (X % 2 == 0) while(X % 2 == 0) X /= 2;
if (X == 1) {
cout << "2\n";
continue;
}
auto factor = Factorize::Pollard_Rho(X);
auto prime_divisor = factor;
prime_divisor.erase(unique(prime_divisor.begin(), prime_divisor.end()), prime_divisor.end());
long long result = 2;
for (auto& i : prime_divisor) {
long long temp = upper_bound(factor.begin(), factor.end(), i) -
lower_bound(factor.begin(), factor.end(), i);
temp = temp * 2 + 1;
result *= temp;
}
cout << result << '\n';
}
return 0;
}(C++20, 52ms, 2032KB, 제출번호 68319887)
처음에 $q \leq 5$ 까지만 풀고 일반화를 했더니 참 많이도 틀려버렸습니다.