.

数学推导将问题转化为：

$$ans = \sum_{m \mid s} \left[ f(m) \times \frac{g(m)}{m} \right]$$

其中：

• $$f(m) = \sum_{y|m} y \times \mu(y)$$

• $$g(m) = \sum_{\substack{t \in A \\ m|t}} t$$

我们需要预处理 $f$ 和 $g$ 数组，然后对于每次查询只需枚举因数计算即可

code:

#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize(3,"Ofast")
using namespace std;
template<class T>vector<vector<T>>vertices(size_t n){return vector<vector<T>>(n);}

const int maxa = 1e7 + 5;
int min_prm[maxa], mu[maxa];
int f[maxa], g[maxa]; // f(m)=∑(y|m) y*μ(y),g(m)=∑(t∈A且m|t)t
vector<int> _prm;

int gcd(int a,int b){ while (b!=0) { a%=b;swap(a,b); }return a; }
void pre_mobius() {
    mu[1] = 1;
    for (int i(2); i<maxa; ++i) {
        if (!min_prm[i]) {
            min_prm[i]=i;
            _prm.push_back(i);
            mu[i]=-1;
        }
        for (int j(0); j<_prm.size()&&_prm[j]<=min_prm[i]&&i*_prm[j]<maxa; ++j) {
            min_prm[i*_prm[j]] = _prm[j];
            if (_prm[j]==min_prm[i]) mu[i*_prm[j]]=0;
            else mu[i*_prm[j]] = -mu[i];
        }
    }
}

// 预处理f(m)=∑(y|m) y*μ(y)
void pre_f() {
    for (int y(1); y<maxa; ++y) {
        if (mu[y]==0) continue;
        auto v(y*mu[y]);
        for (int m(y); m<maxa; m+=y) f[m]+=v;
    }
}

// 预处理g(m)=∑(t∈A且m|t) t
void pre_g(const vector<int>& a) {
    for (auto t:a) 
        for (int m(1); m*m<=t; ++m) 
            if (t%m==0) { g[m]+=t; if (m!=t/m) g[t/m]+=t;}
}

vector<int> get_divs(int s) {
    vector<int> divs;
    for (int i(1); i*i<=s; ++i) {
        if (s%i==0){ divs.push_back(i); if (i!=s/i) divs.push_back(s/i); }
    }
    return divs;
}

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pre_mobius();
    pre_f();
    int n;
    cin>>n;
    vector<int> a(n);
    int max_v(0);
    for (int i(0); i<n; ++i) {
        cin>>a[i];
        max_v=max(max_v,a[i]);
    }  
    // 预处理g数组，注意只要处理到max a[i]即可
    pre_g(a);
    int m;
    cin >> m;
    for (int q(0); q<m; ++q) {
        int b;
        cin>>b;
        int ans(0);
        vector<int> divs;
    for (int i(1); i*i<=b; ++i) {
        if (b%i==0){ divs.push_back(i); if (i!=b/i) divs.push_back(b/i); }
    }
        // ∑(m|b) [f(m)*g(m)/m]
        for (auto m : divs) {
            if (m>max_v) continue; 
            ans += f[m]*(g[m]/m);
        }
        cout << ans << '\n';
    }
}