Submission #3570192

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>

#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;

using namespace std;
typedef pair<int, int> pii;

ll gcd(ll a, ll b){
    if(b > a){
        return gcd(b, a);
    }
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}


int main(){
    ll N, K;
    cin >> N >> K;
    map<ll,ll> mp;
    rep(i, N){
        ll a;
        cin >> a;
        ll g = gcd(a, K);
        mp[g] ++;
    }

    ll ans = 0;
    for(auto iter = mp.begin(); iter != mp.end(); iter ++){
        for(auto iter2 = mp.begin(); iter2 != mp.end(); iter2 ++){
            ll k1 = iter -> first;
            ll k2 = iter2 -> first;
            if(k1 * k2 % K == 0){
                if(iter == iter2){
                    ll tmp =  1L * (iter -> second);
                    ans += tmp * tmp - tmp;
                }else{
                    ans += 1L * (iter -> second) * (iter2 -> second);
                }
            }
        }
    }
    cout << ans / 2 << endl;

    return 0;
}

Submission Info

Judge Result