모듈러 거듭제곱 (Subtask 1-5)
첫 번째부터 다섯 번째 서브태스크는 주어진 모듈러 값 \(P\)에 대해 \(19^x \pmod P\)를 계산하는 문제입니다. 각 서브태스크별로 \(P\) 값의 특성이 달라지며, 이에 따라 접근 방식이 변화합니다.
Subtask 1-3: \(P=998244353\) 고정
이 서브태스크는 \(P=998244353\)로 고정된 경우입니다. 지수 \(x\)의 크기가 매우 클 수 있으므로, 페르마의 소정리(\(a^{P-1} \equiv 1 \pmod P\) for prime \(P\) and \(P\)의 배수가 아닌 \(a\))를 활용하여 지수를 \(P-1\)로 나눈 나머지로 변환해야 합니다. 즉, \(x\)를 입력받을 때부터 \(P-1\)로 나눈 나머지 값을 취하는 전략이 필요합니다. 이는 일반적인 모듈러 거듭제곱(Modular Exponentiation) 함수를 통해 효율적으로 계산할 수 있습니다.
Subtask 4: 미지의 작은 \(P\) 탐색
네 번째 서브태스크는 \(19^x \pmod P\)를 계산해야 하지만, 모듈러 \(P\) 값이 주어지지 않습니다. 출력값의 범위가 대략 \(10^6\) 정도임을 단서로 활용할 수 있습니다. 주어진 첫 번째 입력값과 그에 대한 출력값을 사용하여 \(1\)부터 \(10^6\)까지의 모든 정수를 \(P\)로 가정하고 모듈러 거듭제곱을 역으로 계산해보면, 실제 모듈러 값 \(P=1145141\)을 찾아낼 수 있습니다.
Subtask 5: 미지의 큰 \(P\) 탐색
다섯 번째 서브태스크는 앞서와 동일하게 \(19^x \pmod P\)를 구하지만, 모듈러 \(P\)가 \(5 \times 10^{18}\) 규모로 매우 크기 때문에 단순 브루트 포스는 어렵습니다. 여기서 관찰을 통해 해결 방법을 찾을 수 있습니다. 입력값 \(x\)들 중 차이가 \(k\)인 두 쌍을 찾습니다. 예를 들어, \(x_1\)과 \(x_2 = x_1 + 2\)가 주어지고 각각의 출력값이 \(A\)와 \(B\)라고 가정해 봅시다.
이는 다음 관계를 만족합니다:
\(A \cdot 19^2 \equiv B \pmod P\)
이 식을 변형하면, \(A \cdot 361 - B = nP\) (여기서 \(n\)은 정수) 형태가 됩니다.
좌변 \(A \cdot 361 - B\)는 매우 큰 값이 될 수 있으며, 일반적인 \(long\ long\) 자료형으로는 오버플로가 발생할 가능성이 있습니다. 이때는 \(long\ double\)을 사용하여 근사치를 계산하거나, 오버플로를 방지하는 큰 숫자 곱셈 함수를 사용해야 합니다. 계산된 값 \(A \cdot 361 - B\)는 \(P\)의 배수이므로, \(P\)는 해당 값의 약수 중 하나가 됩니다. \(n\) 값이 비교적 작은 범위(예: 100-200)에 있음을 확인하고, 근사치 \((A \cdot 361 - B) / n\) 주변의 숫자들을 시도해 보며 모듈러 값이 올바른지 검증합니다. 이 과정을 통해 실제 모듈러 \(P=5211600617818708273\)를 찾을 수 있습니다.
정수 오버플로 및 순환 주기 탐색 (Subtask 6-7)
여섯 번째와 일곱 번째 서브태스크는 \(19^x \pmod{998244353}\)를 구하는 것이 아니라, \(int\)형 변수를 사용하여 반복적으로 \(19\)를 곱하고 모듈러 연산을 수행할 때 발생하는 \(int\)형 오버플로를 그대로 반영한 결과를 요구합니다. 즉, 중간 계산 과정에서 오버플로가 발생하더라도 이를 무시하고 다음 계산에 사용하는 방식입니다. 다음 의사 코드와 같습니다.
val = (int)((unsigned int)val * 19) % 998244353;여섯 번째 서브태스크는 \(x\) 값이 작으므로 위 연산을 직접 반복하여 계산할 수 있습니다.
하지만 일곱 번째 서브태스크는 \(x\)가 매우 커서 직접 반복하는 것은 불가능합니다. 이러한 형태의 순환식은 결국 특정 시점부터 반복되는 순환 주기를 갖게 됩니다. 예를 들어, \(x=55246\) 이후부터 \(45699\)개의 값이 순환하는 패턴을 발견할 수 있습니다. 충분히 많은 횟수(예: \(10^6\)회)를 미리 계산하여 순환 시작점과 주기를 파악한 후, \(x\)가 클 경우 이 순환 패턴을 이용하여 결과를 얻을 수 있습니다.
원시근 탐색 (Subtask 14-16)
열네 번째부터 열여섯 번째 서브태스크는 주어진 범위 \(l\)부터 \(r\) 사이의 정수 중에서 모듈러 \(P\)에 대한 원시근(Primitive Root)을 찾는 문제입니다.
Subtask 14: 고정된 \(P=998244353\)
\(P=998244353\)는 소수이며, 오일러 피 함수 \(\varphi(P) = P-1 = 998244352 = 2^{23} \times 7 \times 17\)입니다. \(\varphi(P)\)의 소인수 개수가 적으므로, 원시근의 정의에 따라 임의의 정수 \(a\)가 원시근인지 판별하기 위해 \(\varphi(P)\)의 모든 소인수 \(p_i\)에 대해 \(a^{(\varphi(P)/p_i)} \not\equiv 1 \pmod P\)를 만족하는지 직접 검사할 수 있습니다.
Subtask 15: 고정된 \(P=13123111\) (많은 소인수)
이 경우 \(P=13123111\)는 소수이며, \(\varphi(P) = 13123110 = 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 19 \times 23\)로, 소인수가 많고 검사해야 할 숫자의 범위가 \(10^7\)에 달해 직접 판별하는 것은 비효율적입니다. 이럴 때는 하나의 원시근 \(g\)를 찾아낸 후(예: \(g=6\)), 나머지 원시근들은 \(g^t \pmod P\) 형태임을 활용합니다. 이때 \(g^t\)가 원시근이 되려면 \(t\)와 \(\varphi(P)\)가 서로소여야 합니다. 따라서 \(\varphi(P)\)의 소인수들을 이용하여 \(t\)와 서로소인지 빠르게 판별할 수 있으며, 이 방법으로 모든 원시근을 효율적으로 찾아낼 수 있습니다.
Subtask 16: 미지의 \(P\) 및 원시근 활용
마지막 서브태스크에서는 모듈러 \(P\)가 미지수입니다. 힌트는 \(P\)가 \(10^9\)에서 \(2 \times 10^9\) 사이의 소수임을 알려줍니다. 주어진 원시근이 있다고 가정하고, 해당 범위 내의 모든 수를 탐색하며 소수 여부를 밀러-라빈(Miller-Rabin)으로 검사하고, 후보 \(P\)에 대해 주어진 원시근이 실제로 원시근이 될 수 있는지 확인합니다. 예를 들어, \(g^{(P-1)/2} \not\equiv 1 \pmod P\)와 같은 조건을 활용하여 가능한 \(P\)를 추려낼 수 있습니다. 이 과정을 통해 \(P=1515343657\)와 같은 값을 찾아낼 수 있으며, 이후에는 열네 번째 서브태스크와 동일한 방식으로 원시근을 찾습니다.
소수 판별 (Subtask 8-10)
여덟 번째부터 열 번째 서브태스크는 주어진 범위 \(l\)부터 \(r\) 사이의 각 숫자가 소수인지 판별하는 문제입니다.
작은 범위의 숫자들에 대해서는 에라토스테네스의 체(Sieve of Eratosthenes)와 같은 선형 체(Linear Sieve) 알고리즘을 사용하여 효율적으로 소수를 판별할 수 있습니다.
하지만 범위가 넓어지거나 숫자의 크기가 커질 경우에는 밀러-라빈(Miller-Rabin) 소수 판별법이 유용합니다. 밀러-라빈은 확률적 알고리즘으로, \(O((\log N)^3)\) 정도의 시간 복잡도로 숫자가 소수인지 판별할 수 있으며, 테스트 횟수 \(k\)에 따라 오판 확률이 \(1/4^k\)로 줄어듭니다. 일반적으로 몇 개의 고정된 밑(base)을 사용하여 테스트하면 매우 높은 정확도로 실용적인 시간 안에 소수 여부를 판단할 수 있습니다. 이 문제에서는 대략 2-3개의 밑으로도 충분히 통과할 수 있습니다.
뫼비우스 함수 계산 (Subtask 11-13)
열한 번째부터 열세 번째 서브태스크는 주어진 범위 \(l\)부터 \(r\) 사이의 각 숫자에 대한 뫼비우스 함수(\(\mu\)) 값을 계산하는 문제입니다.
작은 범위에 대해서는 선형 체를 통해 \(\mu\) 값을 미리 계산할 수 있지만, 최대 \(10^{18}\)에 달하는 큰 숫자에 대해서는 직접 체를 적용하기 어렵습니다. 이러한 큰 숫자에 대한 뫼비우스 함수를 계산하기 위해서는 \(\sqrt{N_{max}}\) (예: \(10^{18}\)의 경우 \(10^9\))까지의 소수들을 미리 체로 걸러내는 전략이 필요합니다.
주어진 숫자 \(N\)을 \(10^9\) 이하의 소인수들로 나눈 후 남은 몫을 \(val\)이라고 하겠습니다. 이때 \(val\)은 다음 세 가지 경우 중 하나에 해당합니다. (단, \(val > 1\))
- \(val\)이 소수인 경우: \(10^9\)보다 큰 소수는 많지 않으므로, 밀러-라빈 소수 판별법으로 \(val\)이 소수인지 확인합니다. 이 경우 \(\mu\) 값에 추가적으로 \(-1\)이 곱해집니다.
- \(val\)이 두 개의 서로 다른 소수의 곱인 경우: \(val = p_1 \cdot p_2\) (여기서 \(p_1, p_2 > 10^9\)이며 \(p_1 \neq p_2\))입니다. 이 경우 \(\mu\) 값은 변화가 없습니다 (\((-1) \times (-1) = 1\) 효과).
- \(val\)이 소수의 제곱인 경우: \(val = p^2\) (여기서 \(p > 10^9\))입니다. 이 경우 뫼비우스 함수 정의에 따라 \(\mu(N)\)은 \(0\)이 됩니다. 제곱근을 이용한 판별로 확인할 수 있습니다.
이러한 방식으로 \(l\)부터 \(r\)까지의 모든 숫자에 대해 뫼비우스 함수 값을 계산할 수 있습니다. 특히, 제곱 인수를 포함하는 숫자는 \(\mu\) 값이 \(0\)이 되므로, 이를 정확히 처리하는 것이 중요합니다.
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#lt;cstring> // For memset
#include <cstdio> // For getchar
// 타입 별칭 정의
using long_long = long long;
using unsigned_long_long = unsigned long long;
// --- 모듈러 연산 헬퍼 함수 ---
// 모듈러 덧셈: (a + b) % p
inline void add_mod(unsigned_long_long &a, unsigned_long_long b, unsigned_long_long p) {
a += b;
if (a >= p) a -= p;
}
// 모듈러 곱셈: (a * b) % p (비트 연산을 이용한 효율적인 구현)
unsigned_long_long modular_multiply(unsigned_long_long factor_a, unsigned_long_long factor_b, unsigned_long_long modulus) {
unsigned_long_long result = 0;
factor_a %= modulus;
factor_b %= modulus;
while (factor_b > 0) {
if (factor_b & 1) {
add_mod(result, factor_a, modulus);
}
add_mod(factor_a, factor_a, modulus);
factor_b >>= 1;
}
return result;
}
// 모듈러 거듭제곱: (base^exp) % p
unsigned_long_long modular_power(unsigned_long_long base, unsigned_long_long exponent, unsigned_long_long modulus) {
unsigned_long_long result = 1;
base %= modulus;
while (exponent > 0) {
if (exponent & 1) result = modular_multiply(result, base, modulus);
base = modular_multiply(base, base, modulus);
exponent >>= 1;
}
return result;
}
// 큰 지수 X를 (모듈러-1)로 나눈 나머지를 읽는 함수
unsigned_long_long read_large_exponent_mod(unsigned_long_long reduced_modulus) {
unsigned_long_long value = 0;
char char_input;
while (!isdigit(char_input = getchar())); // 숫자 문자가 나올 때까지 건너뛴다
while (isdigit(char_input)) {
value = (value * 10 + (char_input - '0'));
if (value >= reduced_modulus) { // 읽는 도중 모듈러 연산 적용
value %= reduced_modulus;
}
char_input = getchar();
}
return value;
}
// --- Subtask 1-5 해결 로직: 다양한 P에 대한 모듈러 거듭제곱 ---
void solve_modular_exponentiation(unsigned_long_long current_modulus_P) {
int num_queries;
std::cin >> num_queries;
for (int i = 0; i < num_queries; ++i) {
unsigned_long_long exponent_val = read_large_exponent_mod(current_modulus_P - 1); // X mod (P-1) 읽기
std::cout << modular_power(19, exponent_val, current_modulus_P) << "\n";
}
}
// --- Subtask 6-7 해결 로직: 정수 오버플로 및 순환 주기 감지 ---
void solve_int_overflow_cycle() {
int num_queries;
std::cin >> num_queries;
// 순환 주기 감지를 위한 수열 미리 계산
const int CYCLE_START_INDEX = 55246; // 순환 시작점
const int CYCLE_LENGTH = 45699; // 순환 길이
std::vector<int> sequence_cache(CYCLE_START_INDEX + CYCLE_LENGTH + 5);
sequence_cache[0] = 1; // 19^0
for (int i = 1; i < sequence_cache.size(); ++i) {
// 문제의 요구사항인 int 오버플로 시뮬레이션:
// (unsigned int)로 캐스팅하여 32비트 unsigned 정수 범위 내에서 곱셈을 수행하면 오버플로 시 정확히 2^32로 나눈 나머지가 됨
unsigned int intermediate_product = (unsigned int)sequence_cache[i-1] * 19;
sequence_cache[i] = (int)(intermediate_product % 998244353);
}
for (int q = 0; q < num_queries; ++q) {
long_long input_exponent_val;
std::cin >> input_exponent_val;
if (input_exponent_val < sequence_cache.size()) {
std::cout << sequence_cache[input_exponent_val] << "\n";
} else {
// 순환 주기 활용: (입력 지수 - 순환 시작점) % 순환 길이 + 순환 시작점
long_long effective_index = (input_exponent_val - CYCLE_START_INDEX) % CYCLE_LENGTH + CYCLE_START_INDEX;
std::cout << sequence_cache[effective_index] << "\n";
}
}
}
// --- Subtask 14-16 해결 로직: 원시근 탐색 ---
namespace PrimitiveRootFinder {
// int 타입을 위한 모듈러 거듭제곱 함수
int modular_power_int(int base, int exponent, int modulus) {
int result = 1;
base %= modulus;
while (exponent > 0) {
if (exponent & 1) result = (long_long)result * base % modulus;
base = (long_long)base * base % modulus;
exponent >>= 1;
}
return result;
}
// 숫자의 모든 고유 소인수를 구하는 함수
std::vector<int> get_distinct_prime_factors(int number) {
std::vector<int> factors;
for (int i = 2; (long_long)i * i <= number; ++i) {
if (number % i == 0) {
factors.push_back(i);
while (number % i == 0) {
number /= i;
}
}
}
if (number > 1) {
factors.push_back(number);
}
return factors;
}
// 'num'이 'modulus'의 원시근인지 확인하는 함수 (modulus는 소수여야 함)
bool check_primitive_root(int candidate_num, int modulus, const std::vector<int>& prime_factors_of_phi) {
if (candidate_num <= 1 || std::gcd(candidate_num, modulus) != 1) return false;
int phi_val = modulus - 1; // 소수 P에 대해 phi(P) = P-1
for (int factor : prime_factors_of_phi) {
if (modular_power_int(candidate_num, phi_val / factor, modulus) == 1) {
return false; // 원시근 조건 불만족
}
}
return true; // 원시근
}
// 고정된 P에 대해 L부터 R까지 원시근을 찾는 함수
void solve_for_fixed_P(int lower_bound, int upper_bound, int current_P) {
std::vector<int> phi_factors = get_distinct_prime_factors(current_P - 1);
for (int i = lower_bound; i <= upper_bound; ++i) {
std::cout << (check_primitive_root(i, current_P, phi_factors) ? 'g' : '.');
}
std::cout << "\n";
}
// P=13123111과 같이 소인수가 많은 경우, 모든 원시근을 미리 계산하여 출력하는 함수
void solve_for_many_factors_P(int current_P) {
std::vector<bool> is_primitive_root_flags(current_P, false);
// 문제의 풀이에서 g=6을 사용하여 순환하는 방식으로 원시근을 탐색했음.
// 6^t가 원시근이 되는 t는 phi(P)와 서로소인 경우.
int current_power_val = 6; // 6^1부터 시작
int exponent_count = 0;
int phi_val = current_P - 1;
std::vector<int> phi_factors_for_exponent = get_distinct_prime_factors(phi_val);
do {
exponent_count++;
bool is_exponent_coprime = true;
for (int factor : phi_factors_for_exponent) {
if (exponent_count % factor == 0) {
is_exponent_coprime = false;
break;
}
}
if (is_exponent_coprime) {
is_primitive_root_flags[current_power_val] = true;
}
current_power_val = (long_long)current_power_val * 6 % current_P;
} while (current_power_val != 6); // 6^t가 다시 6^1이 될 때까지 반복
for (int i = 1; i < current_P; ++i) {
std::cout << (is_primitive_root_flags[i] ? 'g' : '.');
}
std::cout << "\n";
}
} // namespace PrimitiveRootFinder
// --- Subtask 8-10 해결 로직: 밀러-라빈 소수 판별 ---
namespace PrimalityTester {
// long long 타입을 위한 모듈러 곱셈: (a * b) % p
// (a*b)가 ULLONG_MAX를 초과할 수 있는 경우 long double을 사용하여 오버플로를 방지
long_long modular_multiply_ll(long_long factor_a, long_long factor_b, long_long modulus) {
factor_a %= modulus;
factor_b %= modulus;
long_long result_val = factor_a * factor_b - (long_long)((unsigned long long)((long double)factor_a * factor_b / modulus) * modulus);
if (result_val < 0) {
result_val += modulus;
} else if ((unsigned long long)result_val >= (unsigned long long)modulus) {
result_val -= modulus;
}
return result_val;
}
// long long 타입을 위한 모듈러 거듭제곱: (base^exp) % p
long_long modular_power_ll(long_long base, long_long exponent, long_long modulus) {
long_long result = 1;
base %= modulus;
while (exponent > 0) {
if (exponent & 1) result = modular_multiply_ll(result, base, modulus);
base = modular_multiply_ll(base, base, modulus);
exponent >>= 1;
}
return result;
}
// 밀러-라빈 소수 판별 테스트
bool miller_rabin_test(long_long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;
long_long d = n - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
// 특정 범위의 N에 대해 충분한 검증을 제공하는 테스트 밑(bases) 집합
// N이 3.8 * 10^16 이하일 때 {2, 3, 5, 7, 11, 13, 17, 19, 23}로 충분.
// long long 범위 전체를 커버하려면 더 많은 밑이 필요.
long_long test_bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (long_long a : test_bases) {
if (a >= n) break;
long_long x = modular_power_ll(a, d, n);
if (x == 1 || x == n - 1) continue;
bool is_prime_witness = false;
for (int r = 1; r < s; ++r) {
x = modular_multiply_ll(x, x, n);
if (x == n - 1) {
is_prime_witness = true;
break;
}
}
if (!is_prime_witness) return false; // 'a'는 합성수임을 증명하는 증인
}
return true; // 매우 높은 확률로 소수
}
void solve_primality_queries() {
int num_queries;
std::cin >> num_queries;
while (num_queries--) {
long_long l_range, r_range;
std::cin >> l_range >> r_range;
for (long_long i = l_range; i <= r_range; ++i) {
std::cout << (miller_rabin_test(i) ? 'p' : '.');
}
std::cout << "\n";
}
}
} // namespace PrimalityTester
// --- Subtask 11-13 해결 로직: 뫼비우스 함수 계산 ---
namespace MobiusFunctionCalculator {
const int SMALL_PRIME_SIEVE_LIMIT = 1000000;
std::vector<int> smallest_prime_factor_sieve(SMALL_PRIME_SIEVE_LIMIT + 1);
std::vector<int> prime_list;
void generate_small_primes() {
std::iota(smallest_prime_factor_sieve.begin(), smallest_prime_factor_sieve.end(), 0); // 초기화: spf[i]=i
for (int i = 2; i <= SMALL_PRIME_SIEVE_LIMIT; ++i) {
if (smallest_prime_factor_sieve[i] == i) { // i가 소수인 경우
prime_list.push_back(i);
}
for (int p : prime_list) {
if (p > smallest_prime_factor_sieve[i] || (long_long)i * p > SMALL_PRIME_SIEVE_LIMIT) {
break;
}
smallest_prime_factor_sieve[i * p] = p; // 합성수의 가장 작은 소인수 업데이트
}
}
}
// 숫자가 특정 한계보다 큰 소수의 제곱인지 확인 (예: 10^6보다 큰 소수 p에 대해 p^2)
bool is_large_prime_squared(long_long n_val) {
if (n_val <= 1) return false;
long_long root_n = round(sqrt(n_val));
if (root_n * root_n == n_val) {
// 제곱근이 소수이고, 작은 소수 체 한계를 넘는 큰 소수인지 확인
return PrimalityTester::miller_rabin_test(root_n) && root_n > SMALL_PRIME_SIEVE_LIMIT;
}
return false;
}
void solve_mobius_queries() {
generate_small_primes(); // 작은 소수 리스트 한 번만 생성
int num_queries;
std::cin >> num_queries;
while (num_queries--) {
long_long lower_bound, upper_bound;
std::cin >> lower_bound >> upper_bound;
// 뫼비우스 값과 남은 인수들을 저장할 배열
std::vector<int> current_mobius_values(upper_bound - lower_bound + 1);
std::vector current_remaining_factors(upper_bound - lower_bound + 1);
for (long_long i = lower_bound; i <= upper_bound; ++i) {
current_mobius_values[i - lower_bound] = 1; // 초기 μ(N) = 1 (모든 인수가 1일 때)
current_remaining_factors[i - lower_bound] = i; // 남은 인수는 자기 자신부터 시작
}
// 작은 소수들을 사용하여 범위 내의 숫자들에 대해 뫼비우스 값 처리
for (int p_val : prime_list) {
long_long p_squared = (long_long)p_val * p_val;
// p^2으로 나누어지는 수들은 μ=0
long_long start_for_p_sq = (lower_bound + p_squared - 1) / p_squared * p_squared;
for (long_long j = start_for_p_sq; j <= upper_bound; j += p_squared) {
current_mobius_values[j - lower_bound] = 0;
}
// p로 나누어지는 수들은 μ에 -1을 곱함
long_long start_for_p = (lower_bound + p_val - 1) / p_val * p_val;
for (long_long j = start_for_p; j <= upper_bound; j += p_val) {
if (current_mobius_values[j - lower_bound] != 0) { // 이미 0이 된 수는 건너뛴다
current_mobius_values[j - lower_bound] *= -1;
// 현재까지 처리되지 않은 남은 인수를 업데이트
current_remaining_factors[j - lower_bound] /= p_val;
}
}
}
// 작은 소인수 분해 후 남은 인수에 대해 처리
for (long_long i = lower_bound; i <= upper_bound; ++i) {
long_long offset_idx = i - lower_bound;
if (current_mobius_values[offset_idx] == 0) {
std::cout << '0';
continue;
}
long_long remaining_factor_val = current_remaining_factors[offset_idx];
if (remaining_factor_val == 1) { // 모든 소인수가 SMALL_PRIME_SIEVE_LIMIT 이하
std::cout << (current_mobius_values[offset_idx] == 1 ? '+' : '-');
} else {
// 남은 인수가 1보다 큰 경우: 큰 소수, 두 개의 큰 소수 곱, 또는 큰 소수의 제곱
if (PrimalityTester::miller_rabin_test(remaining_factor_val)) { // Case 1: 남은 인수가 큰 소수
std::cout << (current_mobius_values[offset_idx] * -1 == 1 ? '+' : '-');
} else if (is_large_prime_squared(remaining_factor_val)) { // Case 3: 남은 인수가 큰 소수의 제곱
std::cout << '0';
} else { // Case 2: 남은 인수가 두 개의 서로 다른 큰 소수의 곱
// (remaining_factor_val이 소수가 아니고, 소수의 제곱도 아니면,
// 문제의 범위 제한(10^18)과 sieve_limit(10^6)에 따라 두 개의 다른 소수 곱일 수밖에 없음)
std::cout << (current_mobius_values[offset_idx] == 1 ? '+' : '-');
}
}
}
std::cout << "\n";
}
}
} // namespace MobiusFunctionCalculator
// --- 메인 함수: 입력 태그에 따라 서브태스크별 로직 실행 ---
int main() {
std::ios_base::sync_with_stdio(false); // C++ 스트림과 C 스트림 동기화 해제
std::cin.tie(NULL); // cin, cout 묶음 해제 (입출력 속도 향상)
srand(time(0)); // 밀러-라빈 테스트 등에서 필요할 수 있는 난수 생성기 시드 설정
char input_tag_str[15];
std::cin >> input_tag_str; // 서브태스크 식별자 문자열 읽기
if (strcmp(input_tag_str, "1_998244353") == 0) {
solve_modular_exponentiation(998244353ULL);
} else if (strcmp(input_tag_str, "1?") == 0) {
solve_modular_exponentiation(1145141ULL);
} else if (strcmp(input_tag_str, "1?+") == 0) {
solve_modular_exponentiation(5211600617818708273ULL);
} else if (strcmp(input_tag_str, "1wa_998244353") == 0) {
solve_int_overflow_cycle();
} else if (strcmp(input_tag_str, "2g") == 0) {
int num_queries;
std::cin >> num_queries;
while (num_queries--) {
int l_val, r_val, p_val;
std::cin >> l_val >> r_val >> p_val;
if (p_val == 998244353) {
PrimitiveRootFinder::solve_for_fixed_P(l_val, r_val, p_val);
} else { // 문제의 맥락상 P=13123111을 의미
PrimitiveRootFinder::solve_for_many_factors_P(p_val);
}
}
} else if (strcmp(input_tag_str, "2g+") == 0) {
int num_queries;
std::cin >> num_queries;
for (int q_idx = 0; q_idx < num_queries; ++q_idx) {
int l_val, r_val, p_val;
std::cin >> l_val >> r_val;
if (q_idx < num_queries - 1) { // 마지막 쿼리가 아닌 경우 P를 입력받음
std::cin >> p_val;
} else { // 마지막 쿼리인 경우 P는 1515343657로 고정
p_val = 1515343657;
}
PrimitiveRootFinder::solve_for_fixed_P(l_val, r_val, p_val);
}
} else if (strcmp(input_tag_str, "2p") == 0) {
PrimalityTester::solve_primality_queries();
} else if (strcmp(input_tag_str, "2u") == 0) {
MobiusFunctionCalculator::solve_mobius_queries();
}
return 0;
}