結果
| 問題 |
No.1871 divisXor
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:03:16 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,819 bytes |
| コンパイル時間 | 1,002 ms |
| コンパイル使用メモリ | 90,800 KB |
| 実行使用メモリ | 132,300 KB |
| 最終ジャッジ日時 | 2025-05-14 13:05:55 |
| 合計ジャッジ時間 | 7,902 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | TLE * 2 |
| other | TLE * 29 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <map>
// Use __int128 for intermediate calculations in Miller-Rabin power function to avoid overflow with large moduli
typedef long long ll;
/*
* Miller-Rabin Primality Test for 64-bit integers
* Uses __int128 for modular exponentiation intermediate products.
*/
// Modular exponentiation: (base^exp) % modulus
ll power(ll base, ll exp, ll modulus) {
ll res = 1;
base %= modulus;
while (exp > 0) {
if (exp % 2 == 1) res = (__int128)res * base % modulus;
base = (__int128)base * base % modulus;
exp /= 2;
}
return res;
}
// Checks if 'a' is a witness that 'n' is composite.
// n is the number to test, a is the base, d and s are such that n-1 = d * 2^s with d odd.
bool check_composite(ll n, ll a, ll d, int s) {
ll x = power(a, d, n); // Calculate a^d % n
// If a^d % n = 1 or a^d % n = n-1, n might be prime.
if (x == 1 || x == n - 1)
return false;
// Check for a^(d * 2^r) % n == n-1 for r from 1 to s-1
for (int r = 1; r < s; r++) {
x = (__int128)x * x % n; // Square x modulo n
if (x == n - 1)
return false; // Might be prime
}
// If none of the conditions are met, n is definitely composite.
return true;
}
// Deterministic Miller-Rabin primality test for n < 2^64
bool is_prime(ll n) {
if (n < 2) return false; // Primes are >= 2
// Find d and s such that n-1 = d * 2^s where d is odd
int s = 0;
ll d = n - 1;
while ((d & 1) == 0) { // While d is even
d >>= 1; // Divide d by 2
s++; // Increment s
}
// Use a standard set of bases proven sufficient for deterministic check for n < 2^64
// Bases from https://miller-rabin.appspot.com/
// Using fewer bases {2, 7, 61} is sufficient for n < 2^32, but use larger set for safety up to 2^64.
for (ll a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
if (n == a) return true; // Handle cases where n is one of the bases (which are prime)
if (a % n == 0) continue; // Base 'a' is a multiple of 'n', provides no info
// Check if 'a' is a witness for compositeness of 'n'
if (check_composite(n, a, d, s))
return false; // Found a witness, n is composite
}
// If no witness found after checking all required bases, n is prime for n < 2^64
return true;
}
/*
* Precomputation of sum of divisors function f(k) = sigma_1(k)
*/
// K_limit is the search limit for k in strategies 5' and 6.
// MAXK is the array size for precomputation, needs to be at least 2*K_limit + 1.
const int K_limit = 2000000;
const int MAXK = 4000005;
std::vector<ll> f_values(MAXK); // Stores f(k) for k < MAXK
// Map to quickly find the smallest k for a given f(k) value.
std::map<ll, ll> f_to_k;
// Precompute f(k) values using a sieve-like method to find prime factorizations
void precompute_f() {
// Sieve to find the smallest prime factor (SPF) for each number up to MAXK-1
std::vector<int> min_prime_factor(MAXK);
std::vector<int> primes; // List of prime numbers found
for (int i = 2; i < MAXK; ++i) {
if (min_prime_factor[i] == 0) { // If i is prime
min_prime_factor[i] = i;
primes.push_back(i);
}
// Mark multiples of primes found so far
for (int p : primes) {
// Optimization: If p > SPF[i], then i*p will be marked later by SPF[i].
if (p > min_prime_factor[i] || (ll)i * p >= MAXK) break;
min_prime_factor[i * p] = p;
}
}
// Base case f(1) = 1
f_values[1] = 1;
if (f_to_k.find(1) == f_to_k.end()) {
f_to_k[1] = 1;
}
// Compute f(k) for k from 2 to MAXK-1 using the multiplicative property
// f(k) = f(p1^e1) * f(p2^e2) * ... where k = p1^e1 * p2^e2 * ...
// f(p^e) = 1 + p + p^2 + ... + p^e
for (int k = 2; k < MAXK; ++k) {
int current_k = k;
ll total_f = 1; // Initialize f(k)
while (current_k > 1) { // While there are prime factors left
int p = min_prime_factor[current_k]; // Get smallest prime factor
ll p_power = 1; // Holds p^i
ll f_p_e = 0; // Holds sum of divisors for p^e
// Calculate f(p^e) = 1 + p + ... + p^e
while (current_k > 0 && current_k % p == 0) {
f_p_e += p_power; // Add p^i to the sum
p_power *= p; // Update p_power to p^(i+1)
current_k /= p; // Divide out the factor p
}
f_p_e += p_power; // Add the last term p^e
total_f *= f_p_e; // Update total_f using multiplicative property
}
f_values[k] = total_f; // Store computed f(k)
// Store the smallest k found for this value of f(k) in the map
if (f_values[k] >= 0 && f_to_k.find(f_values[k]) == f_to_k.end()) {
f_to_k[f_values[k]] = k;
}
}
}
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Perform precomputation
precompute_f();
ll N;
std::cin >> N; // Read input N
// Handle N=0: No solution possible because sum of positive integers must be positive.
if (N == 0) {
std::cout << -1 << std::endl;
return 0;
}
// Handle N=1: Solution A=(1) works. f(1)=1. Sum = 1 < 2*1.
if (N == 1) {
std::cout << 1 << std::endl; // M=1
std::cout << 1 << std::endl; // A_1=1
return 0;
}
/*
* Try strategies to find sequence A.
*/
// Strategy 2: If N-1 is prime (for N >= 2), A=(N-1) is a solution.
// f(N-1) = (N-1)+1 = N. Sum = N-1. N-1 < 2N is true for N >= 1.
if (N >= 2) {
ll N_minus_1 = N - 1;
// Check N-1 > 0 and primality using Miller-Rabin
if (N_minus_1 > 0 && is_prime(N_minus_1)) {
std::cout << 1 << std::endl; // M=1
std::cout << N_minus_1 << std::endl; // A_1 = N-1
return 0;
}
}
// Strategy 3: Check if N = f(k) for some small k using the precomputed map.
// If found, A=(k) is a solution. f(k)=N. Sum=k. k <= f(k)=N. For N >= 1, k < 2N.
if (f_to_k.count(N)) {
ll k = f_to_k[N];
std::cout << 1 << std::endl; // M=1
std::cout << k << std::endl; // A_1 = k
return 0;
}
// Strategy 4: Check if f(k) = N ^ 1 for some small k > 1.
// If found, A=(1, k) is a solution. f(1) ^ f(k) = 1 ^ (N^1) = N. Sum = 1+k. Need 1+k < 2N.
ll N_xor_1 = N ^ 1;
if (f_to_k.count(N_xor_1)) {
ll k = f_to_k[N_xor_1];
if (k > 1) { // k must be distinct from 1.
// Check sum condition. Long long is sufficient as 2*N fits.
if (1 + k < 2 * N) {
std::cout << 2 << std::endl; // M=2
std::cout << 1 << " " << k << std::endl; // A = (1, k)
return 0;
}
}
}
// Strategy 5': Find smallest k > 1 such that f(k) ^ f(2k) = N ^ 1.
// If found, A=(1, k, 2k) is a solution. f(1)^f(k)^f(2k) = 1 ^ (N^1) = N.
// Sum = 1+k+2k = 1+3k. Need 1+3k < 2N.
for (ll k = 2; k <= K_limit; ++k) {
// Ensure 2*k is within precomputed range
if (2*k >= MAXK) break;
ll fk = f_values[k];
ll f2k = f_values[2*k];
// Check if XOR matches target N^1
if ((fk ^ f2k) == N_xor_1) {
// Check sum condition. Long long is sufficient.
if (1 + 3 * k < 2 * N) {
std::cout << 3 << std::endl; // M=3
std::cout << 1 << " " << k << " " << 2 * k << std::endl; // A = (1, k, 2k)
return 0;
}
}
}
// Strategy 6: Find smallest k1 > 1, then smallest k2 > 1 such that f(k1) ^ f(k2) = N.
// If found, A=(k1, k2) is a solution. f(k1)^f(k2) = N. Sum = k1+k2. Need k1+k2 < 2N.
for (ll k1 = 2; k1 <= K_limit; ++k1) {
ll fk1 = f_values[k1];
ll V = N ^ fk1; // Target value for f(k2)
// Look up V in the map to find a suitable k2
if (f_to_k.count(V)) {
ll k2 = f_to_k[V];
// Ensure k2 > 1 and k1, k2 are distinct
if (k2 > 1 && k1 != k2) {
// Check sum condition. Long long is sufficient.
if (k1 + k2 < 2 * N) {
std::cout << 2 << std::endl; // M=2
std::cout << k1 << " " << k2 << std::endl; // A = (k1, k2)
return 0;
}
}
}
}
// If none of the strategies provided a solution
std::cout << -1 << std::endl;
return 0;
}