Hướng dẫn giải của Good Pair

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ả: nguyenttuca

Yêu cầu của bài toán: ~a_i~ chia hết cho ~b_j\times k~.

Nhận xét 1: ~a_i~ phải là bội của ~b_j \times k~.
Nhận xét 2: ~a_i~, ~b_j~ ~\le 10^6~ ~\Rightarrow~ ta có thể áp dụng đếm phân phối cho ~2~ mảng này.

Từ Nhận xét 1 và Nhận xét 2 ta có được thuật toán như sau: Với mỗi ~b_j~: Duyệt tất cả các bội của ~b_j \times k~ và đếm xem có bao nhiêu giá trị ~a_i~ bội của ~b_j \times k~.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 3;

int n, m, k, a[maxn], b[maxn], c[1000005];
long long Ans;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define NAME ""
    if(fopen(NAME".INP", "r")){
        freopen(NAME".INP", "r", stdin);
        freopen(NAME".OUT", "w", stdout);
    }
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        c[a[i]]++;
    }
    for(int i = 1; i <= m; i++) cin >> b[i];
    int ln = *max_element(a + 1, a + n + 1);
    for(int i = 1; i <= m; i++){
        for(int j = b[i] * k; j <= ln; j += b[i] * k){
            Ans += c[j];
        }
    }
    cout << Ans;
    return 0;
}

Bình luận

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

0

altaltalt đã bình luận lúc 9, Tháng 12, 2024, 2:21

thuật này TLE nhé, ví dụ test ~n=10^5, k=1~ và mảng ~a~ và ~b~ gồm ~10^5-1~ số ~1~ và ~1~ số ~10^5~