結果
| 問題 |
No.3038 シャッフルの再現
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,915 bytes |
| コンパイル時間 | 1,365 ms |
| コンパイル使用メモリ | 106,704 KB |
| 実行使用メモリ | 9,344 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:33 |
| 合計ジャッジ時間 | 7,588 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 20 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <cmath> // For std::abs, std::sqrt
#include <cstdlib> // For std::rand, std::srand
#include <ctime> // For std::time
#include <numeric> // For std::gcd
#include <algorithm> // For std::max
// Use __int128 for intermediate calculations where standard long long might overflow
using ll = long long;
// The modulus for the final answer
ll P_MOD = 1e9 + 7;
// Modular exponentiation: computes (base^exp) % P_MOD
ll power(ll base, ll exp) {
ll res = 1;
base %= P_MOD;
if (base < 0) base += P_MOD; // Ensure base is non-negative
while (exp > 0) {
if (exp % 2 == 1) res = (__int128)res * base % P_MOD;
// Avoid unnecessary squaring at the end when exp becomes 1
if (exp > 1) {
base = (__int128)base * base % P_MOD;
}
exp /= 2;
}
return res;
}
// Modular exponentiation: computes (base^exp) % m for a specific modulus m
ll power_mod(ll base, ll exp, ll m) {
if (m == 1) return 0; // Modulo 1 is always 0
__int128 res = 1;
base %= m;
if (base < 0) base += m; // Ensure base is non-negative
while (exp > 0) {
if (exp % 2 == 1) res = res * base % m;
if (exp > 1) {
base = (__int128)base * base % m;
}
exp /= 2;
}
return (ll)res;
}
// Matrix struct for 2x2 matrices used in Fibonacci calculations
struct Matrix {
ll mat[2][2];
Matrix() {
mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
}
// Returns the identity matrix
static Matrix identity() {
Matrix I;
I.mat[0][0] = I.mat[1][1] = 1;
return I;
}
// Matrix multiplication with modulo m
Matrix multiply(const Matrix& other, ll m) const {
Matrix result;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
// Use __int128 to prevent overflow during multiplication
result.mat[i][j] = (result.mat[i][j] + (__int128)mat[i][k] * other.mat[k][j]);
// Keep intermediate values within check to avoid large numbers before final modulo
if (result.mat[i][j] >= 2*m || result.mat[i][j] <= -2*m)
result.mat[i][j] %= m;
}
// Apply final modulo and ensure non-negativity
result.mat[i][j] %= m;
if (result.mat[i][j] < 0) result.mat[i][j] += m;
}
}
return result;
}
// Equality comparison for matrices
bool operator==(const Matrix& other) const {
return mat[0][0] == other.mat[0][0] && mat[0][1] == other.mat[0][1] &&
mat[1][0] == other.mat[1][0] && mat[1][1] == other.mat[1][1];
}
};
// Matrix exponentiation: computes (base^exp) % m
Matrix matrix_pow(Matrix base, ll exp, ll m) {
if (m == 1) return Matrix(); // Return zero matrix for mod 1
Matrix res = Matrix::identity();
while (exp > 0) {
if (exp % 2 == 1) res = res.multiply(base, m);
base = base.multiply(base, m);
exp /= 2;
}
return res;
}
// Miller-Rabin primality test
// Bases {2, 3, 5, 7, 11} are sufficient for N < 25,326,001
// which covers the max required bound of 2 * (10^7 + 1)
bool is_prime(ll n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
ll d = n - 1;
while (d % 2 == 0) d /= 2;
auto check = [&](ll a) {
ll x = power_mod(a, d, n);
if (x == 1 || x == n - 1) return true;
ll current_d = d;
while (current_d != n - 1) {
x = (__int128)x * x % n;
current_d *= 2;
if (x == 1) return false; // Found non-trivial sqrt of 1 mod n
if (x == n - 1) return true;
}
return false; // Failed witness test
};
for (ll a : {2, 3, 5, 7, 11}) {
if (n == a) return true; // n is one of the bases
if (a >= n) break; // Don't test bases larger than n
if (!check(a)) return false; // Found a witness, n is composite
}
return true; // Likely prime
}
// Pollard's Rho algorithm for integer factorization
// Returns a non-trivial factor of n, or -1 on failure (e.g., finding n itself)
// Takes starting c value to allow retries with different parameters
ll pollard_rho(ll n, ll c_start) {
ll x = 2, y = 2, d = 1;
ll c = c_start; // Parameter for the pseudo-random function
// The function g(x) = (x^2 + c) mod n
auto f = [&](ll val) {
__int128 temp = (__int128)val * val;
temp = (temp + c) % n;
return (ll)temp;
};
// Floyd's cycle-finding algorithm
while (d == 1) {
x = f(x);
y = f(f(y)); // y moves twice as fast as x
d = std::gcd(std::abs(x - y), n); // Check GCD periodically
}
// If d == n, Pollard's Rho failed with this c. Caller should retry.
if (d == n) return -1;
return d; // Found a non-trivial factor d
}
// Optimized factorization using trial division + Pollard Rho
std::map<ll, int> factorize_optimized(ll n) {
std::map<ll, int> factors;
if (n <= 1) return factors;
ll current_n = n;
// Step 1: Trial division for small primes up to a limit (e.g., 1000)
ll limit = 1000;
for (ll i = 2; i <= limit && i * i <= current_n; ++i) {
if (current_n % i == 0) {
while (current_n % i == 0) {
factors[i]++;
current_n /= i;
}
}
}
// If fully factored, return
if (current_n == 1) return factors;
// Step 2: If n is still large, use Miller-Rabin + Pollard's Rho
std::vector<ll> q; // Stack for factors to process
q.push_back(current_n);
ll c_pollard = 1; // Initial c value for Pollard's Rho
while(!q.empty()){
ll curr = q.back();
q.pop_back();
if (curr == 1) continue;
// Check if the current number is prime
if(is_prime(curr)){
factors[curr]++;
continue;
}
// If composite, find a factor using Pollard's Rho
ll factor = pollard_rho(curr, c_pollard);
// Retry mechanism if Pollard's Rho fails (returns -1)
while(factor == -1) {
c_pollard++; // Try next c value
factor = pollard_rho(curr, c_pollard);
}
// Push the found factor and the remaining part onto the stack
if (factor > 1) { // Ensure factor is valid
q.push_back(factor);
q.push_back(curr / factor);
} else {
// This indicates a critical failure, potentially a bug
std::cerr << "Factorization critical failure for: " << curr << std::endl;
// As a dangerous fallback, consider curr might be a prime power or issue with implementation
factors[curr]++; // Add curr itself, likely incorrect but avoids crash
}
}
return factors;
}
// Helper function to combine factor maps for LCM calculation
// Updates total_factors with maximum exponents from new_factors
void combine_factors(std::map<ll, int>& total_factors, const std::map<ll, int>& new_factors) {
for (const auto& pair : new_factors) {
total_factors[pair.first] = std::max(total_factors.count(pair.first) ? total_factors[pair.first] : 0, pair.second);
}
}
// Find Pisano period pi(p) for prime p
ll find_pisano_period(ll p) {
// Handle base cases
if (p == 2) return 3;
if (p == 5) return 20;
// Determine the upper bound for the period based on p mod 5
ll bound;
ll p_mod_5 = p % 5;
if (p_mod_5 == 1 || p_mod_5 == 4) { // Case Legendre symbol (5/p) = 1
bound = p - 1;
} else { // Case Legendre symbol (5/p) = -1
bound = 2 * (p + 1);
}
// Factorize the bound
std::map<ll, int> bound_factors = factorize_optimized(bound);
ll period = bound; // Start with the maximal possible period
Matrix T; // Fibonacci matrix T = {{1, 1}, {1, 0}}
T.mat[0][0] = 1; T.mat[0][1] = 1;
T.mat[1][0] = 1; T.mat[1][1] = 0;
Matrix I = Matrix::identity(); // Identity matrix
// Iterate through prime factors of the bound to find the minimal period
for (auto const& [q, e] : bound_factors) {
// Check if period is divisible by q before trying to reduce it
if (period % q != 0) continue;
ll test_period = period / q;
Matrix T_pow = matrix_pow(T, test_period, p); // Compute T^(period/q) mod p
// While T^(period/q) is Identity, it means the period is smaller. Reduce period.
while (T_pow == I) {
period = test_period;
// Check if further division by q is possible
if (period % q != 0) break;
test_period /= q;
if (period == 0) { // Safety check, should not happen
std::cerr << "Error: Period became zero." << std::endl;
return 1; // Return 1 as a fallback period?
}
T_pow = matrix_pow(T, test_period, p);
}
}
return period; // The final minimal period
}
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Seed random number generator for Pollard's Rho (optional if using deterministic c start)
// std::srand(std::time(0));
int N; // Number of prime factors of M
std::cin >> N;
// Map to store the prime factorization of the final LCM
std::map<ll, int> total_factors;
for (int i = 0; i < N; ++i) {
ll p; // Prime factor of M
int k; // Exponent of p in M's factorization
std::cin >> p >> k;
// Find the Pisano period for the prime p
ll pi_p = find_pisano_period(p);
// Factorize pi(p)
std::map<ll, int> current_pi_factors = factorize_optimized(pi_p);
// Apply the formula pi(p^k) = p^(k-1) * pi(p)
// Update the factors map by adding p with exponent k-1
if (k > 1) {
current_pi_factors[p] += (k - 1);
}
// Combine the factors into the total factors map for LCM calculation
combine_factors(total_factors, current_pi_factors);
}
// Compute the final LCM modulo P_MOD from its prime factorization
ll final_lcm = 1;
for (auto const& [prime_factor, exponent] : total_factors) {
if (exponent == 0) continue; // Skip factors with exponent 0
// Compute prime_factor^exponent mod P_MOD
ll term = power(prime_factor, exponent);
// Multiply into the final LCM result
final_lcm = (__int128)final_lcm * term % P_MOD;
}
// Output the final result
std::cout << final_lcm << std::endl;
return 0;
}