# [Solution] Mã hóa - Encryption

## Subtask 1 và 2:
**Ý tưởng và cài đặt:** Ta trâu qua mọi $S$ mà $L ≤ S ≤ R$ và đếm số lượng thỏa yêu cầu đề bài

Độ phức tạp: $O(R - L)$.

### Code mẫu:

#include <bits/stdc++.h>

using namespace std;

// Function to count numbers between l and r such that a * s % k == 0
long long countMultiples(long long a, long long k, long long l, long long r) {
    int dem = 0;
    for(int i = l; i <= r; ++i) {
        if (a * i % k == 0) ++dem;
    }
    return dem;
}

int main() {
    freopen("ENCRYPTION.inp", "r", stdin);
    freopen("ENCRYPTION.out", "w", stdout);
    long long a, k, l, r;
    cin >> l >> r >> a >> k;

    long long result = countMultiples(a, k, l, r);
    cout << result;

    return 0;
}

## Subtask 3:
**Ý tưởng:**
- Đặt $P = LCM(A, K)$
- $A \times S$ $mod$ $k = 0$. Vậy $A \times S$ là bội của $P$. Khi đó, $A \times S$ sẽ có dạng $A \times S = x \times P$ với $x$ là số nguyên.
$\Rightarrow A \times S = x \times \frac{A * K}{\gcd(A, K)}$
$\Rightarrow S = x \times \frac{K}{\gcd(A, K)}$
- Kết quả bài toán sẽ là số lượng $x$ sao cho $L ≤ x \times \frac{K}{\gcd(A, K)} ≤ R$, tương đương với số lượng số nguyên trong khoảng $[l, r]$ chia hết cho $K / \gcd(A, K)$.

Độ phức tạp: $O(log (min(a, k)))$.

### Code mẫu:

#include <bits/stdc++.h>

using namespace std;

long long countMultiples(long long a, long long k, long long l, long long r) {
    long long g = __gcd(a, k);
    g = k / g;
    return (r / g) - (l -1) / g;
}

int main() {
    freopen("ENCRYPTION.inp", "r", stdin);
    freopen("ENCRYPTION.out", "w", stdout);
    long long a, k, l, r;
    cin >> l >> r >> a >> k;

    long long result = countMultiples(a, k, l, r);
    cout << result << endl;

    return 0;
}