题意:长度为n的序列a,定义f(x) 为x的各个数位相乘.

n<=2e5, 0<=a[i],k<=1e18. 问有多少对(i,j) 满足f(a[i])*f(a[j]) 可以表示为某个自然数的k次幂.

 

f(x)= a1^p1 * a2^p2...ak^pk. f(y)=a1^q1*a2^q2..ak^qk

那么f(x)*f(y)为某个x的k次幂, 则p1+q1肯定为k的倍数 .

因为ai只有4种可能,2,3,5,7. 用4维数组或者map<vector<int>,int> 保存每个数的质因子幂的状态,求下每个幂关于k的补集即可.

0^0=1 特判k==0的状态即可.

#include 
     
      using namespace std;typedef long long ll;typedef pair
      
        ii;const int N=2e5+5,M=19;ll n,k,x,pw[N];ll mp[M*3][M*2][M][M];int main(){	ios::sync_with_stdio(false);cin.tie(0);	cin>>n>>k;	ll res=0,zero=0,one=0;		for(ll i=1;i<=n;i++){		cin>>x;		bool flag=false;		if(x==0)	flag=true;		int p2=0,p3=0,p5=0,p7=0,tmp=0,ind=0;		while(x){			int r=x%10;			ind++;			x/=10;			if(r==0)	flag=true;			if(r==1)	tmp++;			if(r==2)	p2++;			if(r==3)	p3++;			if(r==4)	p2+=2;			if(r==5)	p5++;			if(r==6)	p2++,p3++;			if(r==7)	p7++;			if(r==8)	p2+=3;			if(r==9)	p3+=2;		}		if(flag){			if(k!=0)	res+=i-1;			zero++;			continue;		}		if(k==0){			if(ind==tmp)				res+=one,one++;			continue;		}		p2%=k;		p3%=k;		p5%=k;		p7%=k;		int q2=k-p2,q3=k-p3,q5=k-p5,q7=k-p7;		q2%=k;		q3%=k;		q5%=k;		q7%=k;		if(q2<=18*3&&q3<=18*2&&q5<=18&&q7<=18)			res+=mp[q2][q3][q5][q7];		res+=zero;		//cout<
       <<' '<
        
         <<' '<
         
          <<' '<<' '<
          
           <<'\n'; mp[p2][p3][p5][p7]++; } //cout<
           
            <<'\n'; ll sum=n*(n-1)/2-res; cout<
            
             <<'\n'; return 0;}