优化满足x*z>y²的三元组计数的高性能求解方案（X,Y,Z≤1000）

Hey there! Let's tackle this performance problem together. The triple-loop approach works but is way too slow for large values (like 1000 each, that's a billion iterations—yikes!). Here's how we can optimize it drastically:

Core Optimization Idea #

Instead of checking every possible triple (x,y,z) directly, we can use mathematical insights to cut down the number of computations:

1. Calculate the total number of valid triples (all combinations of x,y,z within bounds): total = X * Y * Z
2. Calculate the number of invalid triples where x*z ≤ y²
3. Subtract the invalid count from the total to get the answer: answer = total - invalid_count

The key win is optimizing how we compute the invalid count for each y using integer division block processing (also known as "divisor block splitting"), which reduces per-y computations from O(X) to O(√(y²)) = O(y) — a massive improvement.

Optimized Code Implementation #

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    istringstream iss(s);
    vector<int> v((istream_iterator<int>(iss)), istream_iterator<int>());
    int X = v[0], Y = v[1], Z = v[2];
    
    // Total valid triples without any conditions
    unsigned long long total = (unsigned long long)X * Y * Z;
    unsigned long long invalid = 0;
    
    for (int y = 1; y <= Y; ++y) {
        long long y_squared = (long long)y * y; // Avoid integer overflow
        unsigned long long invalid_for_y = 0;
        int x = 1;
        
        // Use integer division blocks to compute sum of min(Z, floor(y²/x))
        while (x <= X) {
            if (y_squared / x == 0) {
                // For x > y², floor(y²/x) is 0, so no invalid z values
                break;
            }
            int quotient = y_squared / x;
            // Find the largest x' where floor(y²/x') == quotient
            int block_end = min(y_squared / quotient, X);
            int block_size = block_end - x + 1;
            // Add the number of invalid (x,z) pairs for this block
            invalid_for_y += (unsigned long long)block_size * min((long long)Z, (long long)quotient);
            x = block_end + 1;
        }
        
        invalid += invalid_for_y;
    }
    
    unsigned long long answer = total - invalid;
    cout << answer << endl;
    return 0;
}

How It Works #

For each y:

1. Compute y² (stored as long long to prevent overflow for large y)
2. For each block of x values where floor(y²/x) is the same, we calculate how many z values are invalid (i.e., z ≤ floor(y²/x)) in one go instead of iterating each x individually.
3. Sum these invalid counts for all blocks, then add to the total invalid triple count.

Performance Gain #

• Original approach: O(XYZ) time — 1 billion operations for X=Y=Z=1000.
• Optimized approach: O(Y*√(Y)) time — roughly 1 million operations for X=Y=Z=1000, which is 1000x faster.

Test Case Verification #

For input 3 3 3:

• Total triples: 27
• Invalid triples: 1 (y=1) +6 (y=2)+9(y=3) =16
• Answer: 27-16=11, which matches manual counting of valid triples.

内容的提问来源于stack exchange，提问作者nop