Tìm số có K ước số lẻ trong khoảng cho trước trong C++

Giới thiệu

Cho ba số nguyên L, R và k. Tìm số lượng số trong khoảng [L, R] có chính xác k ước số, trong đó k là số lẻ.

Quan sát quan trọng: Một số có số ước lẻ nếu và chỉ nếu nó là số chính phương (perfect square). Do đó ta chỉ cần kiểm tra các số chính phương trong khoảng.

Ví dụ minh họa

Đầu vào

a = 3, b = 10, k = 3

Đầu ra

2

Giải thích

Các số có đúng 3 ước trong khoảng 3-10:
4: ước = 1, 2, 4
9: ước = 1, 3, 9

Phương pháp giải

Chỉ duyệt các số chính phương trong khoảng [a, b], đếm ước của chúng và so sánh với k.

Chương trình minh họa

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

bool isPerfectSquare(int n) {
    int s = sqrt(n);
    return (s*s == n);
}

int countDivisors(int n) {
    int divisors = 0;
    for (int i = 1; i <= sqrt(n) + 1; i++) {
        if (n % i == 0) {
            divisors++;
            if (n / i != i)
                divisors++;
        }
    }
    return divisors;
}

int countNumberKDivisors(int a, int b, int k) {
    int numberCount = 0;
    for (int i = a; i <= b; i++) {
        if (isPerfectSquare(i))
            if (countDivisors(i) == k)
                numberCount++;
    }
    return numberCount;
}

int main() {
    int a = 3, b = 10, k = 3;
    cout << "The count of numbers with K odd divisors is " << countNumberKDivisors(a, b, k);
    return 0;
}

Đầu ra

The count of numbers with K odd divisors is 2