結果
| 問題 |
No.1632 Sorting Integers (GCD of M)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,335 bytes |
| コンパイル時間 | 1,010 ms |
| コンパイル使用メモリ | 75,448 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:03:56 |
| 合計ジャッジ時間 | 2,747 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 49 WA * 10 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <utility> // Required for std::swap in gcd function
// Function to compute (base^exp) % mod using binary exponentiation (also known as exponentiation by squaring)
// This is efficient for large exponents.
long long power(long long base, long long exp) {
long long res = 1;
long long P = 1000000007; // Define the modulus P
base %= P; // Reduce base modulo P initially
while (exp > 0) {
// If exp is odd, multiply base with result
if (exp % 2 == 1) res = (res * base) % P;
// Square the base and halve the exponent
base = (base * base) % P;
exp /= 2;
}
return res;
}
// Function to compute modular multiplicative inverse using Fermat's Little Theorem
// This theorem states that if P is a prime number, then for any integer a not divisible by P,
// a^(P-1) === 1 (mod P). Therefore, a^(P-2) === a^(-1) (mod P).
// This works because P = 10^9 + 7 is a prime number.
long long modInverse(long long n) {
long long P = 1000000007; // Define the modulus P
// P - 2 = 1000000005 is the exponent needed for modular inverse
return power(n, P - 2);
}
// Standard Euclidean algorithm to compute the Greatest Common Divisor (GCD) of two numbers.
long long gcd(long long a, long long b) {
// The algorithm relies on the property gcd(a, b) = gcd(b, a % b)
while (b) { // Loop continues as long as b is non-zero
a %= b; // Replace a with a mod b
std::swap(a, b); // Swap a and b
}
// When b becomes 0, a holds the GCD
return a;
}
int main() {
// Use faster I/O operations by disabling synchronization with C stdio and uncoupling cin/cout.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
long long N; // Total number of digits
std::cin >> N;
// Store counts of digits 1 through 9. Index 0 is unused.
std::vector<long long> c(10);
// Store the distinct digits that are present (have count > 0)
std::vector<int> present_digits;
int distinct_digit_count = 0; // Counter for the number of distinct digits present
int the_digit = -1; // Variable to store the digit value if only one type is present
// Read the counts c_1 through c_9
for (int i = 1; i <= 9; ++i) {
std::cin >> c[i];
// If digit i has a count greater than 0, record it
if (c[i] > 0) {
present_digits.push_back(i);
distinct_digit_count++;
// Keep track of the digit. If distinct_digit_count ends up being 1, this holds the value.
the_digit = i;
}
}
// Define the modulus for output
long long P = 1000000007;
// Check if there is only one distinct digit type present
if (distinct_digit_count == 1) {
// Case: Only one type of digit `i` is present.
// The only possible number M is the one formed by repeating digit `i`, N times.
// The GCD is M itself.
long long i = the_digit;
// Calculate M = i * (1 + 10 + ... + 10^(N-1)) mod P
// The sum is a geometric series sum: (10^N - 1) / (10 - 1) = (10^N - 1) / 9.
// So M = i * (10^N - 1) / 9.
// Calculate M modulo P. Use modular arithmetic properties.
long long term1 = i % P; // The digit i modulo P
long long term2_pow10N = power(10, N); // 10^N mod P
// Calculate (10^N - 1) mod P. Add P before taking modulo to handle potential negative result from subtraction.
long long term2 = (term2_pow10N - 1 + P) % P;
long long term3_inv9 = modInverse(9); // Modular inverse of 9 modulo P
// Compute (term1 * term2 * term3) % P using modular multiplication
long long result = (term1 * term2) % P;
result = (result * term3_inv9) % P;
std::cout << result << std::endl;
} else {
// Case: Multiple types of digits are present.
// Compute the GCD `g` of all present digits values.
long long current_gcd = 0;
for (int digit : present_digits) {
if (current_gcd == 0) {
// Initialize GCD with the first present digit encountered
current_gcd = digit;
} else {
// Update GCD by taking GCD with the next present digit
// Cast digit to long long just to match the function signature, although digits 1-9 fit in int.
current_gcd = gcd(current_gcd, (long long)digit);
}
}
long long S_dig = 0; // Variable to store the sum of all digits (considering their values)
// Calculate the total sum of digits: Sum(i * c_i) for i=1..9
for (int i = 1; i <= 9; ++i) {
// Use long long for the product i * c_i and the total sum S_dig to prevent potential overflow.
// Max S_dig can be 9 * N <= 9 * 10^9, which fits within a 64-bit long long.
S_dig += (long long)i * c[i];
}
long long g = current_gcd; // The GCD of the values of present digits
// The problem reduces to considering digits i/g. Let S'_dig be the sum of these reduced digits.
// S'_dig = Sum (i/g * c_i) = (Sum i*c_i) / g = S_dig / g.
// We need to check divisibility of S'_dig by 3 and 9.
// Ensure g is not 0 before division. Since digits are 1-9, g must be >= 1.
long long S_prime_dig = S_dig / g;
int k = 0; // The exponent for the factor 3 in the final GCD
// Determine the value of k based on divisibility properties of S_prime_dig by 3 and 9.
if (S_prime_dig % 3 == 0) { // Check if S'_dig is divisible by 3
if (S_prime_dig % 9 == 0) { // Check if S'_dig is divisible by 9
k = 2; // If divisible by 9, power of 3 is 2.
} else { // Divisible by 3 but not by 9
k = 1; // Power of 3 is 1.
}
} else { // Not divisible by 3
k = 0; // Power of 3 is 0.
}
// The final GCD G is g * 3^k. Calculate this value modulo P.
long long factor3k = power(3, k); // Calculate 3^k mod P
// Calculate G = (g mod P * 3^k mod P) mod P
long long G = (g % P * factor3k) % P;
std::cout << G << std::endl;
}
return 0;
}