結果
| 問題 |
No.1383 Numbers of Product
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:38 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 15,158 bytes |
| コンパイル時間 | 1,048 ms |
| コンパイル使用メモリ | 106,036 KB |
| 実行使用メモリ | 68,608 KB |
| 最終ジャッジ日時 | 2025-05-14 13:17:43 |
| 合計ジャッジ時間 | 55,394 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 33 TLE * 18 |
コンパイルメッセージ
main.cpp: In function ‘int128 isqrt(int128)’:
main.cpp:122:47: warning: integer overflow in expression of type ‘int128’ {aka ‘__int128’} results in ‘0x7fffffffffffffffffffffffffffffff’ [-Woverflow]
122 | int128 MAX_VAL = (((int128)1) << 127) - 1; // Max positive value for signed __int128_t
| ~~~~~~~~~~~~~~~~~~~~~^~~
main.cpp: In function ‘int main()’:
main.cpp:247:60: warning: integer overflow in expression of type ‘int128’ {aka ‘__int128’} results in ‘0x7fffffffffffffffffffffffffffffff’ [-Woverflow]
247 | int128 MAX_VAL = (((int128)1) << 127) - 1; // Max positive value for signed __int128_t
| ~~~~~~~~~~~~~~~~~~~~~^~~
ソースコード
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <string>
#include <algorithm> // For std::reverse
#include <climits> // Potentially useful constants, though not directly used here for __int128_t limits.
// Check if GCC/Clang provides __int128_t
#if defined(__GNUC__) || defined(__clang__)
#define HAVE_INT128
using int128 = __int128_t;
#else
// Fallback or error if __int128_t is not available.
// The problem constraints (up to 10^18) require 128-bit integers for intermediate calculations like K*K.
#warning "__int128_t not supported. This code might fail due to overflow for large inputs."
// Using long long as a fallback placeholder, but this is insufficient for the problem constraints.
using int128 = long long;
#endif
#ifdef HAVE_INT128
// Function to print __int128_t since standard I/O streams might not support it.
std::ostream& operator<<(std::ostream& os, int128 val) {
if (!val) return os << '0'; // Handle 0 case
std::string s = "";
bool neg = false;
// Handle the minimum value case specially to avoid issues with -val overflowing.
int128 MIN_INT128 = ((int128)1) << 127;
if (val == MIN_INT128) {
// The minimum value for signed 128-bit integer is -(2^127).
return os << "-170141183460469231731687303715884105728";
}
if (val < 0) {
neg = true;
val = -val; // Safe now because val is not MIN_INT128
}
while (val > 0) {
// Append digit corresponding to val % 10
s += (char)('0' + (val % 10));
val /= 10;
}
if (neg) s += '-'; // Prepend '-' if negative
std::reverse(s.begin(), s.end()); // Reverse to get correct order
return os << s;
}
// Input operator for __int128_t. Reads a string and parses it. Basic error handling omitted for brevity.
std::istream& operator>>(std::istream& is, int128& val) {
std::string s;
is >> s;
val = 0;
bool neg = false;
int start_idx = 0;
if (!s.empty() && s[0] == '-') {
neg = true;
start_idx = 1;
}
for (int i = start_idx; i < s.length(); ++i) {
// Basic check for digit; more robust parsing might be needed in production code.
if (isdigit(s[i])) {
val = val * 10 + (s[i] - '0');
} else {
// Handle non-digit character? Assume valid input for competitive programming.
break;
}
}
if (neg) val = -val;
return is;
}
// Computes floor(sqrt(n)) for non-negative n using __int128_t. Uses binary search.
int128 isqrt(int128 n) {
if (n < 0) return 0; // Square root is not defined for negative numbers in integers.
if (n == 0) return 0;
int128 low = 0, high;
// Estimate upper bound for binary search based on bit length for efficiency.
// If n has B bits, sqrt(n) has approximately B/2 bits.
int bits = 0;
if (n > 0) {
// Use GCC/Clang builtins for finding leading zeros if available (faster)
#if defined(__GNUC__) || defined(__clang__)
// Check high 64 bits first
unsigned long long high_bits = (unsigned long long)(n >> 64);
if (high_bits > 0) {
// Calculate bits based on high part + 64
bits = 128 - __builtin_clzll(high_bits);
} else {
// Calculate bits based on low part only
bits = 64 - __builtin_clzll((unsigned long long)n);
}
#else
// Fallback method to find bit length if builtins are not available.
int128 temp = n;
while(temp > 0){
temp >>= 1;
bits++;
}
#endif
} else { bits = 0; } // n=0 has 0 bits effectively.
// Set upper bound for binary search: 2^(bits/2 + 1) is safe.
high = ((int128)1) << (bits / 2 + 1);
int128 ans = 0; // Stores the best candidate for floor(sqrt(n)) found so far.
while(low <= high) {
int128 mid = low + (high - low) / 2; // Calculate midpoint avoiding overflow in sum low+high
if (mid == 0) {
// Handle mid=0 separately. If n>=0, 0 is a potential answer.
if (n >= 0) ans = 0;
low = 1; // Continue search in [1, high]
continue;
}
// Check for potential overflow before squaring mid: mid*mid > MAX_INT128?
int128 MAX_VAL = (((int128)1) << 127) - 1; // Max positive value for signed __int128_t
bool overflow = false;
// Use division test: mid > MAX_VAL / mid to detect if mid*mid would overflow.
// Assumes mid > 0, which is true here.
if (mid > MAX_VAL / mid) {
overflow = true;
}
if (overflow) {
// If mid*mid overflows, mid is definitely too large. Reduce search space upper bound.
high = mid - 1;
} else {
// Safe to calculate mid*mid now.
int128 mid_sq = mid * mid;
if (mid_sq == n) {
return mid; // Found exact integer square root.
} else if (mid_sq < n) {
// mid*mid is too small. mid is a potential candidate for floor(sqrt(n)).
// Try larger values.
ans = mid;
low = mid + 1;
} else { // mid_sq > n
// mid*mid is too large. Reduce search space upper bound.
high = mid - 1;
}
}
}
// After binary search, ans holds the largest integer mid such that mid*mid <= n.
return ans;
}
#endif // HAVE_INT128
int main() {
// Faster I/O operations.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
long long N_ll, K_ll, M_ll;
// Read input values as standard long long.
if (!(std::cin >> N_ll >> K_ll >> M_ll)) return 1; // Basic input validity check.
// Check if the required 128-bit integer type is available. If not, exit.
#ifndef HAVE_INT128
std::cerr << "Error: __int128_t not supported. Cannot handle the problem constraints." << std::endl;
return 1;
#endif
// Convert input values to 128-bit integers.
int128 N = N_ll;
int128 K = K_ll;
int128 M = M_ll;
// Input constraints validation: N, K, M >= 1
if (N_ll <= 0 || K_ll <= 0 || M_ll <= 0) {
// The problem statement implies N, K, M >= 1. If M=0, the answer is always 0 because f(X)>=1 for any X.
// Treat invalid inputs (<=0) as resulting in 0 count.
std::cout << 0 << std::endl;
return 0;
}
// Edge case: If K >= N, the smallest possible product P(1, 1, K) = 1 * (1+K) = 1+K.
// Since K >= N >= 1, we have 1+K > K >= N. So 1+K > N.
// All products P(A, B, K) will be > N. Thus, no X <= N can be generated.
if (K >= N) {
std::cout << 0 << std::endl;
return 0;
}
// Calculate floor(sqrt(N)). This helps determine the approach.
int128 sqrtN = isqrt(N);
// Case 1: K is large (K > floor(sqrt(N))).
// In this case, any product P(A, B, K) with B >= 2 will be > N.
// Proof: P(A, B, K) >= P(1, B, K) >= P(1, 2, K) = 1*(1+K)*(1+2K) > K^2.
// Since K > sqrtN, K^2 > (sqrtN)^2 = N. So P(A, B, K) > N for B >= 2.
// Only B=1 is possible. Products are of the form X = A(A+K).
// For such X, f(X)=1 because B=1 is the only possibility and A is unique for a given X.
// We need to count X such that f(X) = M. This is only possible if M=1.
if (K > sqrtN) {
if (M == 1) {
// Count number of A >= 1 such that A(A+K) <= N.
// Solve A^2 + KA - N <= 0. Positive root of A^2+KA-N=0 is (-K + sqrt(K^2+4N))/2.
// Max A is floor of this root.
int128 discriminant = K*K + 4*N; // K*K can exceed 64 bits, needs int128.
int128 S = isqrt(discriminant);
int128 A_max_1_128 = 0;
// Ensure numerator -K+S is positive before division. S > K iff K^2+4N > K^2 iff 4N > 0, true since N>=1.
if (S > K) {
A_max_1_128 = (-K + S) / 2; // Integer division correctly gives floor.
}
// Convert result to long long. A_max_1 <= sqrt(N) <= 10^9, so it fits.
long long A_max_1 = (long long)A_max_1_128;
std::cout << A_max_1 << std::endl;
} else {
// If M != 1, no X can satisfy f(X) = M.
std::cout << 0 << std::endl;
}
} else { // Case 2: K is relatively small (K <= floor(sqrt(N))). Both B=1 and B>=2 might be possible.
// Map to store frequencies of X values generated by pairs (A, B) with B >= 2.
// Key: X value (long long, since X <= N <= 10^18). Value: frequency (long long for safety with M comparison).
std::map<long long, long long> counts_ge2;
// Iterate through possible B values starting from 2. B cannot be very large.
// B=60 is a safe upper bound since (60+1)! > 10^18. Tighter bound B=19 (20! > 10^18).
for (int B = 2; B <= 60; ++B) {
bool B_loop_break = false; // Flag to break outer loop if A=1 already fails.
// Iterate through possible A values starting from 1.
for (long long A_ll = 1; ; ++A_ll) {
int128 A = A_ll;
int128 current_product = A;
// Optimization: if A itself exceeds N, stop for this B.
if (current_product > N) {
// If even A=1 exceeds N, then no products are possible for this B or larger B.
if (A_ll == 1) B_loop_break = true;
break; // Break A loop for current B.
}
bool ok = true; // Flag indicating if product calculation was successful and within bounds.
// Calculate product P(A, B, K) = A * (A+K) * ... * (A+BK)
for (int i = 1; i <= B; ++i) {
int128 term = A + (int128)i * K; // Calculate next term. Needs 128-bit if K is large.
// Check term validity and potential overflow before multiplication.
int128 MAX_VAL = (((int128)1) << 127) - 1; // Max positive value for signed __int128_t
if (term <= 0) { // Term must be positive. Should not happen for A>=1, K>=1, i>=1.
ok = false; break;
}
// Use division test to check for overflow: current_product > MAX_VAL / term?
// Assumes current_product > 0.
if (current_product > 0 && current_product > MAX_VAL / term) {
ok = false; // Overflow detected.
break;
}
current_product *= term; // Perform multiplication.
// Check if product exceeds N after multiplication.
if (current_product > N) {
ok = false; // Exceeds N.
break;
}
}
if (!ok) {
// If calculation failed for A=1 (overflow or >N), then it will fail for any larger A for this B.
// Also, for larger B, P(1, B', K) will be even larger, so it will also fail.
// Hence, we can break the outer B loop as well.
if (A_ll == 1) B_loop_break = true;
break; // Break A loop for current B.
}
// If product calculation succeeded and current_product <= N.
long long current_product_ll = (long long)current_product; // Convert to long long for map key.
counts_ge2[current_product_ll]++; // Increment frequency count for this X value.
}
if (B_loop_break) break; // If A=1 failed, stop iterating through B values.
}
// Process the generated counts to find the final answer.
long long total_count = 0; // Final answer: count of X values with f(X)=M.
long long count_S1_intersect_Sge2 = 0; // Count of X values that are in both S1 and S>=2 sets.
// Iterate through the map of X values generated from B >= 2.
for (auto const& [X_ll, count] : counts_ge2) {
int128 X = X_ll; // X value from the map.
long long current_count = count; // Frequency count from B >= 2 pairs.
// Check if this X value can also be represented as A(A+K) (i.e., is in S1).
// Solve A^2 + KA - X = 0 for integer A >= 1.
int128 discriminant = K*K + 4*X; // Needs 128-bit.
int128 S = isqrt(discriminant);
bool is_S1 = false; // Flag: true if X is in S1.
if (S * S == discriminant) { // Check if discriminant is a perfect square.
int128 numerator = -K + S;
// Check if numerator is positive and even for A = numerator/2 to be a positive integer.
if (numerator > 0 && numerator % 2 == 0) {
int128 A_sol = numerator / 2;
// Ensure A is indeed positive. Should be true if numerator > 0.
if (A_sol > 0) {
is_S1 = true;
}
}
}
int s1_term = is_S1 ? 1 : 0; // Contribution from B=1 case (0 or 1).
// Total frequency f(X) = contribution from B=1 + frequency from B>=2.
// Compare f(X) with M. Use 128-bit comparison for M.
if ((int128)s1_term + current_count == M) {
total_count++; // Found an X value such that f(X)=M.
}
// Keep track of count of X values that are in S1 and also generated by B>=2.
if (is_S1) {
count_S1_intersect_Sge2++;
}
}
// Finally, account for X values that are *only* representable with B=1 (i.e., in S1 \ S_ge2).
// These X values have f(X) = 1. They contribute to the final answer only if M=1.
if (M == 1) {
// Calculate the total number of X values in S1 (max A such that A(A+K)<=N).
int128 discriminant_N = K*K + 4*N;
int128 S_N = isqrt(discriminant_N);
int128 A_max_1_128 = 0;
if (S_N > K) { // Ensure numerator is positive.
A_max_1_128 = (-K + S_N) / 2;
}
long long A_max_1 = (long long)A_max_1_128; // Convert to long long.
// Number of X values only in S1 = |S1| - |S1 intersect S_ge2|.
// |S1| is A_max_1. |S1 intersect S_ge2| is count_S1_intersect_Sge2.
if (A_max_1 >= count_S1_intersect_Sge2) { // Basic sanity check: Intersection size cannot exceed total size.
long long count_S1_only = A_max_1 - count_S1_intersect_Sge2;
total_count += count_S1_only; // Add count of X values where f(X)=1 (and M=1)
} // else branch: should not happen if logic is correct. Indicates an issue.
}
// Output the final total count.
std::cout << total_count << std::endl;
}
return 0;
}