C++ 解法, 执行用时: 135ms, 内存消耗: 4488K, 提交时间: 2021-12-18 19:39:52

#include<bits/stdc++.h>
#define ll long long
#define mo 998244353
using namespace std;

ll m,c,ans;
int a[100005];
unordered_map<ll,int> ma;
int main(){
	int n;
	cin>>n>>c;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (ll m=c;m<=1e9;m*=c){
		ma.clear();
		for (int i=1;i<=n;i++){
			int v=a[i]%m;
			ans+=ma[v];
			ma[v]++;
		}
	}
	cout<<ans*2;
}

Python3 解法, 执行用时: 1434ms, 内存消耗: 22436K, 提交时间: 2021-12-18 22:50:04

n, c = map(int, input().strip().split())
alist = list(map(int, input().strip().split()))
#alist.sort()
p = c
res = 0
while True:
    modDict = {}
    for num in alist:
        res += modDict.get(num%p, 0)
        modDict[num%p] = modDict.get(num%p, 0) + 1
    if p * c > 1e9: break
    p *= c
print(res * 2)