C++ Bài 13.E1: Cặp số ước chung

Points: 30 (partial)

Time limit: 1.0s

Memory limit: 20M

Author:

Problem type

Cho một số nguyên $N$ , hãy đếm tất cả các cặp $GCD(A,B) = B$ với điều kiện $(1 \leq A, B \leq N)$ . Biết $GCD(A,B)$ là ước chung lớn nhất của $A$ và $B$ .

INPUT FORMAT

Dòng đầu tiên chứa số nguyên $N$ $(1 \leq N \leq 10^6)$ .

OUTPUT FORMAT

In ra một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input

Copy

Output

Copy

Giải thích: Các cặp $(1, 1)$ $(2, 2)$ và $(2, 1)$ .

Ví dụ:

Input

Copy

Output

Copy

Giải thích: Các cặp $(1, 1)$ $(2, 2)$ $(3, 3)$ $(2, 1)$ và $(3, 1)$ .

Giải thích ví dụ mẫu:

Ví dụ 1: (2)
- Các cặp (1, 1), (2, 2), và (2, 1) đều thỏa mãn điều kiện GCD(A, B) = B.
Ví dụ 2: (3)
- Các cặp (1, 1), (2, 2), (3, 3), (2, 1), và (3, 1) đều thỏa mãn điều kiện GCD(A, B) = B.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House

Comments

endc67_fullhouse_dev commented 4 months ago

Copy

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    long long result = 0;

    // Duyệt qua tất cả các giá trị B từ 1 đến N
    for (int B = 1; B <= N; ++B) {
        // Tính số lượng các giá trị A sao cho A = k * B và A ≤ N
        result += N / B;
    }

    cout << result << endl;

    return 0;
}