Hướng dẫn giải của Bedao Mini Contest 14 - EXAMINE

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

~\large lcm(x, y) = gcd(x, y)^2~

~\iff~ ~\Large\frac{x \cdot y}{\mathcal{gcd(x, y)}} = gcd(x, y)^2~

~\iff~ ~\Large\frac{x}{gcd(x, y)} \cdot \frac{y}{gcd(x, y)} = n~

Vì ~\large gcd(\frac{x}{gcd(x, y)} \cdot \frac{y}{gcd(x, y)}) = 1~ nên ta cần tính tìm các cặp ~(a, b)~ sao cho ~a \cdot b = n~ và ~gcd(a, b) = 1~ sau đó nhân với ~n~

Vậy thì ta chỉ cần duyệt qua các ước ~i~ của ~n~ sao cho ~\large gcd(i, \frac{n}{i}) = 1~ và nhân tổng với ~n~. Độ phức tạp là ~\mathcal{O}(\sqrt{n} \cdot \mathcal{log}(n))~. Ta còn có thể cải tiến để bỏ qua phần kiểm tra ~\large gcd(i, \frac{n}{i})~, phần này xin nhường lại cho bạn đọc.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & 1)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }

template<class A, class B> bool maximize(A &a, B b) { return a < b && (a = b, true); }
template<class A, class B> bool minimize(A &a, B b) { return a > b && (a = b, true); }

const int MAXN = 1e5 + 6;
const int MOD = 1e9 + 7;

int t, n;

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * x % MOD;
        n /= 2;
        x = x * x % MOD;
    }
    return res;
}

#define TASK ""
int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #ifdef ONLINE_JUDGE
    //  freopen(TASK".inp","r",stdin);
    //  freopen(TASK".out","w",stdout);
    #endif

    cin >> t;

    while (t--) {
        cin >> n;

        vector<int> p;

        int m = n, x;
        for (int i = 2; i * i <= m; i++) {
            if ((m % i) > 0) continue;
            x = 1;
            while ((m % i) == 0) {
                x = x * i % MOD;
                m /= i;
            }
            p.push_back(x);
        }
        if (m > 1) p.push_back(m % MOD);

        int res = 0, k = sz(p), lim = MASK(k), A, B;
        for (int mask = 0; mask < lim; mask++) {
            A = 1, B = 1;
            for (int i = 0; i < k; i++) {
                if (BIT(mask, i)) {
                    A = A * p[i] % MOD;
                    B = (B * p[i] % MOD * p[i]) % MOD;
                }
                else {
                    B = B * p[i] % MOD;
                    A = (A * p[i] % MOD * p[i]) % MOD;
                }
            }

            res = (res + A + B) % MOD;
        }

        cout << res * pw(2, MOD - 2) % MOD << '\n';
    }

    return 0;
}
//196

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    Thien2009  đã bình luận lúc 7, Tháng 4, 2025, 3:18

    n=1 thi dap la bao nhieu vay


  • -5
    quoc14  đã bình luận lúc 22, Tháng 11, 2022, 7:48

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.