นับคู่มี序ที่ผลคูณน้อยกว่า N ใน C++

ภาพรวมปัญหา

ให้จำนวน N ต้องการนับคู่มี序ของจำนวนเต็มบวก (i, j) ที่ i × j < N

ตัวอย่าง

Input: N = 4

Output: 5

คำอธิบาย: (1,1), (1,2), (1,3), (2,1), (3,1)

Input: N = 100

Output: 473

แนวทางแก้ปัญหา

1. วนลูป i จาก 1 ถึง N-1
2. สำหรับแต่ละ i, j วนจาก 1 ถึงที่ i×j < N → j < N/i
3. จำนวน j ที่เป็นไปได้ = ⌊(N-1)/i⌋
4. รวมทั้งหมด = Σ_{i=1}^{N-1} ⌊(N-1)/i⌋

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int productN(int n) {
    int count = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; i * j < n; j++) {
            count++;
        }
    }
    return count;
}

int main() {
    int N = 6;
    cout << "Ordered pairs with product < N: " << productN(N);
    return 0;
}

ผลลัพธ์

Ordered pairs such that product is less than N: 10

แนวทางที่มีประสิทธิภาพ O(√N)

ใช้เทคนิค Divisor Summatory Function หรือ Harmonic Lemma

Σ_{i=1}^{N-1} ⌊(N-1)/i⌋ สามารถคำนวณได้ใน O(√N) โดยจับกลุ่มค่า ⌊(N-1)/i⌋ ที่เท่ากัน

โค้ด O(√N)

long long productN_fast(long long n) {
    long long count = 0;
    long long m = n - 1;
    for (long long i = 1, last; i <= m; i = last + 1) {
        long long q = m / i;
        last = m / q;
        count += q * (last - i + 1);
    }
    return count;
}

ความซับซ้อน

ข้อมูลเพิ่มเติม

ผลรวมนี้คือ Divisor Summatory Function D(N) = Σ_{i=1}^N ⌊N/i⌋ ซึ่งเกี่ยวข้องกับการนับประมาณจำนวนหาร