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

Output

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

Ví dụ:

Input

Output

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 on Jan. 5, 2025, 7:34 a.m.

#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;
}