C++14(g++5.4) 解法, 执行用时: 199ms, 内存消耗: 2736K, 提交时间: 2019-10-23 21:28:41

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x){
    ll sum = 1;
    while(x){
        sum = sum*(x%10);
        x /= 10;
    }
    return sum;
}
map<vector<ll> , ll> mp;
vector<ll> b(4),v(4);
int a[4] = {2,3,5,7};
int main()
{
    ll n,k;
    cin >> n >> k;
    if(k == 0){
        ll flag = 0;
        for(int i = 0; i < n; i ++){
            ll x;
            cin >> x;
            ll y = f(x);
            if(y == 1) flag ++;
        }
        
        cout << n*(n - 1)/2 - flag*(flag-1)/2 << endl;
    }
    else{
        ll flag = 0;
        ll cnt = 0;
        for(int i = 0; i < n; i ++){
            ll x;
            cin >> x;
            ll y = f(x);
            if(y){
                for(int j = 0; j < 4 ; j ++){
                    v[j] = 0;
                    while(y%a[j] == 0){
                        y /= a[j];
                        v[j] ++;
                    }
                    v[j] %= k;
                    b[j] = (k - v[j])%k;
                }
                cnt += mp[b];
                mp[v] ++;
            }
            else flag ++;
        }
        if(flag)
        cnt = flag*(flag - 1)/2 + cnt + flag*(n - flag);
        cnt = n*(n - 1)/2 - cnt;
        cout << cnt << endl;
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 95ms, 内存消耗: 1888K, 提交时间: 2018-11-23 23:16:27

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL mos[4]={2,3,5,7};
map<vector<LL>,LL>my;

int main()
{
	LL n,k;
	scanf("%lld%lld",&n,&k);
	vector<LL>s1;
	vector<LL>s2;
	s1.resize(4),s2.resize(4);
	int i,j;
	LL t;
	LL cnt=0;
	LL ans=0;
	for(i=0;i<n;i++)
	{
		scanf("%lld",&t);
		LL now=1;
		while(t)
		{
			now*=t%10;
			t/=10;
		}
		if(k==0)
		{
			if(now==1)
				cnt++;
			continue;
		}
		if(now==0)
		{
			cnt++;
			continue;
		}
		for(j=0;j<4;j++)
		{
			int num=0;
			while(now%mos[j]==0)
			{
				now/=mos[j];
				num++;
			}
			num%=k;
			s1[j]=num;
			s2[j]=(k-num)%k;
		}
		ans+=my[s2];
		my[s1]++;
	}	
	if(k==0){
		ans=n*(n-1)/2-cnt*(cnt-1)/2;
	}
	else
	{
		ans=ans+cnt*(n-cnt)+(cnt-1)*cnt/2;
		ans=n*(n-1)/2-ans;
	}
	printf("%lld\n",ans);
	return 0;
}