Submission #7980859

---

Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define MAX(X,Y) (*max_element(X,Y))
#define MIN(X,Y) (*min_element(X,Y))
#define NP(X,Y) next_permutation(X,Y)
#define setp(X,Y) cout<<fixed<<setprecision(Y)<<X;
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N,K;
int A[200010];
map<int,int> H;

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

signed main(){
	cin>>N>>K;
	REP(i,N){
		cin>>A[i];
	}
	REP(i,N){
		A[i]=gcd(A[i],K);
		H[A[i]]++;
	}
	int ans=0;
	for(auto i:H){
		for(auto j:H){
			if((i.first*j.first)%K==0&&i.first<=j.first){
				if(i.first==j.first){
					ans+=i.second*(i.second-1)/2;
				}
				else{
					ans+=i.second*j.second;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result