Submission #6751426

---

Source Code Expand

#include <iostream>
#include <map>
using namespace std;
int GCD(int a, int b){
    while(a%b != 0){
        int t = a%b;
        a = b;
        b = t;
    }
    return b;
}
int main(void){
    int n, k, a;
    long long ans = 0;
    map<int, int> p;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> a;
        p[GCD(a, k)]++;
    }
    for(auto itr = p.begin(); itr != p.end(); itr++){
        long long x = itr->first, y = itr->second;
        auto jtr = itr;
        if((x*x)%k == 0)ans += y*(y-1)/2;
        while(++jtr != p.end()){
            if((x*(jtr->first))%k == 0){
                ans += y * (jtr->second);
            }
        }
    }
    cout << ans << endl;
}

Submission Info

Judge Result