题解 | #Sum Gcd#

由于互质和唯一分解定理，和是没有相同的质因数。

那么可以得出：

本题的做法就是，计算出一个总和，然后对于每一个,需要重新计算自己本身，因为和并不互质，不满足等式1，然后加上即可。

#include <bits/stdc++.h>
using namespace std;
#define close ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long 
#define endl '\n'
#define MAXN 1000010
int n,k;
int a[MAXN];
void solve(){ 
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int res = 0,s = 0;
    for(int i = 0; i < n; i++){
        s += gcd(a[i],k);
    }
    for(int i = 0; i < n; i++){
        res += s - gcd(a[i],k);
        res += gcd(a[i] * a[i],k) / gcd(a[i],k);
    }
    cout << res << endl;
}
signed main(){
    close
    int T = 1;
    while(T--){
        solve();
    }
    
    return 0;
}