Công thức tính số ước nguyên dương của một số

Giả sử số nguyên ~n~ được phân tích thành thừa số nguyên tố: ~ n = p_1 ^ {m_1} \times p_2 ^{m_2} \times\dots\times p_k ^{m_k}. ~

Khi đó số lượng ước nguyên dương của ~n~ là: ~(m_1 + 1)(m_2 + 1)\dots(m_k+1)~.

Đếm ước trong ~\mathcal O(n \log n)~

Ta có thể viết hàm đếm số lượng ước nguyên dương trong ~\mathcal O(\log n)~ như sau:

• Trước tiên, ta chuẩn bị một mảng lưu trước ước nguyên tố nhỏ nhất của mỗi số nguyên ~i~ (tốn ~\mathcal O(n \log \log n)~).
• Với mỗi lần gọi hàm đếm ước cho số nguyên ~i~, ta sẽ chia ~i~ cho ước nguyên tố nhỏ nhất của ~i~ đã được chuẩn bị trước. Ta đếm số lần chia hết của ~i~ cho ước nguyên tố nhỏ nhất của ~i~ đang xét (tức số mũ của thừa số nguyên tố tương ứng).
• Áp dụng công thức đếm ước ở trên, ta tính được số lượng ước nguyên dương của số ~i~ đã xét.

Sử dụng hàm đếm ước ~\mathcal O(\log n)~ ở trên, ta có thể dựng các tập hợp gồm các số có cùng số lượng ước nguyên dương trong đoạn ~[1; n]~ với độ phức tạp ~\mathcal O(n \log n)~.

Đếm số cặp ~(x; y)~ thỏa mãn

Gọi ~m~ là số lượng ước lớn nhất của các số trong đoạn ~[1; n]~.

Ta sẽ xét ~d(x), d(y)~ trong khoảng từ ~[1; m]~, sau đó xét các cặp ~(x; y)~ trong tập hợp các số có cùng số lượng ước nguyên dương tương ứng với ~d(x), d(y)~. Nếu bộ số ~d(x), d(y), x, y~ đang xét thỏa mãn với yêu cầu đề bài thì ta cộng vào kết quả.

Code tham khảo

#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i = k; i <= n; i++)
#define FORR(i,k,n) for(int i = n; i >= k; i--)
#define pb push_back
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define BIT(S, i) (((S)>>(i))&1)
#define MASK(i) ((1ll)<<(i))
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

template<class T> 
    bool maximize(T &a, T b) {
    if (a < b) {a = b; return true;}
    return false;
}

template<class T>
    bool minimize(T &a, T b) {
    if (a > b) {a = b; return true;}
    return false;
}

const int N = 3e5+1;
ll ans, n, k, cnt; vll a[N]; int pr[N], d[N], m;

void minp(){
    FOR(i,2,n) pr[i] = i;
    pr[0] = pr[1] = -1;
    for (int i = 2; i * i <= n; i++){
        if (pr[i] == i){
            for (int j = i * i; j <= n; j += i) pr[j] = i;
        }
    }
}

int demuoc(int n){
    int res = 1;
    while (n > 1){
        int cnt = 1;
        int tmp = pr[n];
        while (n % tmp == 0) n /= tmp, ++cnt;
        res *= cnt;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    freopen("DIVI.INP","r",stdin);
    freopen("DIVI.OUT","w",stdout);

    cin >> n >> k;
    minp();

    FOR(i,1,n) a[demuoc(i)].pb(i), maximize(m, demuoc(i));

    FOR(dx,1,m) FOR(dy,1,m){
        ll tmp = 1LL * k * dx * dy; 
        int i = 0, j = a[dy].size()-1;
        while (i < a[dx].size() && j > -1 && a[dx][i] <= a[dy][j]){
            if (1LL* a[dx][i] * a[dy][j] < tmp) ++i; 
            else ans += (1LL*a[dx][i] * a[dy][j--] == tmp);            
        }
    }

    cout << ans;
}