結果
| 問題 |
No.97 最大の値を求めるくえり
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:18:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 541 ms / 5,000 ms |
| コード長 | 6,703 bytes |
| コンパイル時間 | 1,304 ms |
| コンパイル使用メモリ | 99,444 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:19:30 |
| 合計ジャッジ時間 | 4,093 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath> // For std::sqrt and std::ceil
// PRNG implementation (provided in problem statement)
// State variables for the xor128 pseudo-random number generator
unsigned xor128_x = 123456789, xor128_y = 362436069, xor128_z = 521288629, xor128_w = 88675123;
// xor128 function to generate pseudo-random unsigned integers
unsigned xor128() {
unsigned t = xor128_x ^ (xor128_x << 11);
xor128_x = xor128_y; xor128_y = xor128_z; xor128_z = xor128_w;
return xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8));
}
// Define the modulus P as a constant. P = 100003 is given in the problem statement and is prime.
const int P = 100003;
// Modular exponentiation function: computes (base^exp) % P
// Uses binary exponentiation (also known as exponentiation by squaring) for efficiency.
long long power(long long base, long long exp) {
long long res = 1; // Initialize result
base %= P; // Take base modulo P
while (exp > 0) {
// If exp is odd, multiply result with base
if (exp % 2 == 1) res = (res * base) % P;
// Square the base and take modulo P
base = (base * base) % P;
// Halve the exponent (integer division)
exp /= 2;
}
return res;
}
// Modular multiplicative inverse function: computes n^(-1) mod P
// Uses Fermat's Little Theorem: n^(P-2) % P for prime P and n non-zero mod P.
long long modInverse(long long n) {
// We assume n is in [1, P-1] because the case q=0 is handled separately before calling this.
return power(n, P - 2);
}
// Use std::vector<bool> which is a space-optimized specialization for boolean values.
// It will store presence information for elements {0, ..., P-1}.
std::vector<bool> isPresent;
int main() {
// Use fast I/O operations to speed up reading input.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N, Q; // N: length of sequence A, Q: number of queries
std::cin >> N >> Q;
std::vector<int> A(N); // Sequence A stored in a vector
// Generate sequence A using the provided PRNG function
for (int i = 0; i < N; ++i) {
A[i] = xor128() % P; // Generate random value and take modulo P
}
// Determine a threshold for switching between two strategies.
// A threshold of sqrt(P) is a good heuristic based on complexity analysis.
// Using ceil ensures the threshold is at least sqrt(P).
int threshold = static_cast<int>(std::ceil(std::sqrt(P)));
// For P=100003, sqrt(P) is approx 316.2, so threshold will be 317.
if (N <= threshold) {
// Strategy for small N: Iterate through all elements of A for each query.
// Time complexity per query: O(N). Total time: O(N + QN).
// Since N <= sqrt(P), total time is O(sqrt(P) + Q*sqrt(P)).
for (int i = 0; i < Q; ++i) {
int q; // Current query value
std::cin >> q;
// Handle the q=0 case separately: The maximum value is always 0.
if (q == 0) {
std::cout << 0 << "\n";
continue;
}
int max_val = 0; // Initialize maximum value found so far
// Problem constraints state N >= 1, so A is guaranteed to be non-empty.
if (N > 0) { // This check is technically redundant due to N>=1 constraint but safe to have.
// Initialize max_val with the result from the first element A[0]
max_val = (1LL * q * A[0]) % P; // Use 1LL to promote q to long long for multiplication
// Iterate through the rest of the elements (from index 1)
for (int j = 1; j < N; ++j) {
// Use long long for intermediate product (q * A[j]) to prevent overflow before modulo
long long current_val = (1LL * q * A[j]) % P;
// Update max_val if the current value is larger
if (current_val > max_val) {
max_val = current_val;
}
}
}
// Output the maximum value found for this query
std::cout << max_val << "\n";
}
} else {
// Strategy for large N: Use a boolean array for fast O(1) lookups of element presence.
// Preprocessing time: O(N) to generate A + O(P) to initialize vector<bool> + O(N) to populate it = O(N+P).
isPresent.assign(P, false); // Initialize boolean array of size P to all false. O(P) time.
// Mark elements present in A as true in the boolean array. O(N) time.
for (int a : A) {
isPresent[a] = true;
}
// Process each query using the precomputed presence information.
// Average query time complexity: O(log P + P/|S|), where |S| is number of distinct elements in A.
// Since N > sqrt(P), average query time is expected to be O(log P + sqrt(P)).
// Total time: O(N+P + Q*(log P + sqrt(P))).
for (int i = 0; i < Q; ++i) {
int q; // Current query value
std::cin >> q;
// Handle the q=0 case separately: The maximum value is always 0.
if (q == 0) {
std::cout << 0 << "\n";
continue;
}
// Calculate modular inverse of q needed for the alternative iteration strategy. O(log P) time.
long long qinv = modInverse(q);
// Initialize the maximum k found so far. It should default to 0 just in case.
// Since N > threshold >= 1, A is non-empty and some k value will be found.
int max_k = 0;
// Search for the largest k such that (k * qinv) % P is an element present in A.
// Iterate k downwards from P-1 to 0.
for (int k = P - 1; k >= 0; --k) {
// Calculate potential element a_k = (k * qinv) % P.
// Use 64-bit intermediate type (long long) for k * qinv to prevent overflow.
long long a_k = (static_cast<long long>(k) * qinv) % P;
// Check if the element a_k is present in A using the boolean array (O(1) lookup).
if (isPresent[static_cast<int>(a_k)]) {
max_k = k; // Found the largest k that satisfies the condition
break; // Stop searching as we found the maximum possible k
}
}
// Output the found maximum k value, which corresponds to the maximum (q*a)%P value.
std::cout << max_k << "\n";
}
}
return 0; // Indicate successful execution
}