結果
| 問題 |
No.2075 GCD Subsequence
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:09 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 761 ms / 4,000 ms |
| コード長 | 8,263 bytes |
| コンパイル時間 | 960 ms |
| コンパイル使用メモリ | 87,008 KB |
| 実行使用メモリ | 17,208 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:47 |
| 合計ジャッジ時間 | 12,365 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_map> // Using unordered_map for potentially better average performance
#include <vector>
// Define the modulo constant
const long long MOD = 998244353;
// Define the maximum value for A_i + 1 for array bounds
const int MAXA = 1000001;
// spf[i] will store the smallest prime factor of i
std::vector<int> spf(MAXA);
// Store all primes up to MAXA for faster sieve processing
std::vector<int> primes;
// Sieve of Eratosthenes to precompute the smallest prime factor (SPF) for numbers up to MAXA
void sieve() {
// Initialize spf[i] = i for all i. This indicates potentially prime.
std::iota(spf.begin(), spf.end(), 0);
// Mark 0 and 1 explicitly as they don't have prime factors in the usual sense. Use 0 as a marker.
spf[0] = spf[1] = 0;
// Iterate from 2 up to MAXA-1
for (int i = 2; i < MAXA; ++i) {
// If spf[i] is still i, it means i is prime
if (spf[i] == i) {
primes.push_back(i);
}
// Iterate through primes found so far
// Optimization: Only need to check primes p <= spf[i]
for (int p : primes) {
// If prime p is greater than the smallest prime factor of i,
// then i*p will have spf[i] as its smallest prime factor, not p.
// So we can break early.
// Also check if i*p exceeds the bounds of our array.
if (p > spf[i] || (long long)i * p >= MAXA) {
break;
}
// Mark p as the smallest prime factor of i*p
spf[i * p] = p;
}
}
}
// Function to get the distinct prime factors of n using the precomputed SPF table
std::vector<int> get_prime_factors(int n) {
std::vector<int> factors;
// Handle invalid input or edge cases like n=0, n=1. These have no prime factors > 1.
// Also guard against n being outside the precomputed range [2, MAXA-1].
if (n <= 1 || n >= MAXA) return factors;
// Factorize n using SPF
while (n > 1) {
int p = spf[n];
// Basic safety check: if p is invalid (<= 1), stop factorization.
// This shouldn't happen for n in [2, MAXA-1] with a correct sieve.
if (p <= 1) break;
// Add the distinct prime factor p to our list
factors.push_back(p);
// Divide n by p repeatedly until it's no longer divisible by p.
// Using spf[n] == p check can potentially optimize this division process.
int current_p = p; // Store p, as n changes inside the loop
while (n > 1 && spf[n] == current_p) {
// Divide n by its smallest prime factor p
n /= current_p;
// Optional safety check against division errors, though unlikely here.
}
// Check if n became 1 after division, can break early
if (n == 1) break;
}
return factors;
}
int main() {
// Use faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Precompute SPF table using sieve
sieve();
int N; // Number of elements in the sequence
std::cin >> N;
// Use unordered_map to store the dynamic programming state sums associated with square-free divisors
// Key: A square-free integer d > 1, which is a product of distinct primes.
// Value: The sum (modulo MOD) of dp[j] for all processed indices j < i such that d divides A[j].
std::unordered_map<int, int> D;
long long total_subsequences = 0; // Accumulator for the final answer (total valid subsequences)
// Process each element A_i of the input sequence
for (int i = 0; i < N; ++i) {
int current_A; // Read the current element A_i
std::cin >> current_A;
// Handle the case A_i = 1 separately.
// A subsequence ending with 1 can only be (1) itself, or extend a previous subsequence if the last element was 1.
// But gcd(X, 1) = 1, so it cannot extend any subsequence ending with X > 1.
// Effectively, A_i=1 contributes 1 to the DP value (the subsequence (A_i) itself)
// and doesn't interact with previous elements based on GCD condition.
if (current_A == 1) {
long long current_dp = 1; // dp[i] = 1 for A[i] = 1
total_subsequences = (total_subsequences + current_dp) % MOD;
// No updates needed for D map because 1 has no prime factors > 1.
continue; // Proceed to the next element
}
// Get the distinct prime factors of A_i
std::vector<int> p_factors = get_prime_factors(current_A);
int m = p_factors.size(); // Number of distinct prime factors
// Calculate the sum part of dp[i] using Principle of Inclusion-Exclusion (PIE)
// This sum represents: sum_{j < i, gcd(A_j, A_i) > 1} dp[j]
long long current_sum_dp = 0;
// Iterate through all 2^m - 1 non-empty subsets of the prime factors p_factors
// Each subset corresponds to a square-free divisor d = product of primes in the subset.
for (int j = 1; j < (1 << m); ++j) { // j represents the bitmask for the subset
long long d_prod = 1; // Calculate the product of primes in the current subset
int set_bits = 0; // Count the number of primes in the subset (|K| in PIE formula)
for (int bit = 0; bit < m; ++bit) {
// If the 'bit'-th bit is set in j, include the 'bit'-th prime factor
if ((j >> bit) & 1) {
// Product is guaranteed to fit within standard integer types since max A_i = 10^6
// Max product is product of first 7 primes ~ 510510.
d_prod = d_prod * p_factors[bit];
set_bits++;
}
}
// The key for the map D is the integer product d_prod
int d_key = (int)d_prod;
long long term_val = 0; // Value associated with this divisor d_key from map D
// Check if the key d_key exists in the map D
auto it = D.find(d_key);
if (it != D.end()) {
// If found, use its stored value
term_val = it->second;
}
// Apply the PIE logic: add if |K| is odd, subtract if |K| is even.
if (set_bits % 2 == 1) { // Odd number of factors: add term
current_sum_dp = (current_sum_dp + term_val) % MOD;
} else { // Even number of factors: subtract term
// Ensure result remains non-negative before taking modulo
current_sum_dp = (current_sum_dp - term_val + MOD) % MOD;
}
}
// Calculate dp[i]: 1 (for the subsequence consisting of just A[i]) + the PIE sum computed above.
long long current_dp = (1 + current_sum_dp) % MOD;
// Add the calculated dp[i] to the total count of valid subsequences
total_subsequences = (total_subsequences + current_dp) % MOD;
// Update the D map based on the newly computed dp[i] value.
// This dp[i] value needs to be added to D[d] for all square-free divisors d > 1 of A_i.
// Iterate again through all 2^m - 1 non-empty subsets to get these divisors d.
for (int j = 1; j < (1 << m); ++j) {
long long d_prod = 1; // Calculate the product for the subset divisor
for (int bit = 0; bit < m; ++bit) {
if ((j >> bit) & 1) {
d_prod = d_prod * p_factors[bit];
}
}
int d_key = (int)d_prod; // Map key is the integer product
// Update the map entry D[d_key].
// unordered_map::operator[] inserts a default value (0 for int) if key not present, then adds.
// The computation (D[d_key] + current_dp) % MOD handles both update and insertion correctly.
D[d_key] = (D[d_key] + current_dp) % MOD;
}
}
// Output the final total count of valid subsequences modulo MOD
std::cout << total_subsequences << std::endl;
return 0;
}