C++(g++ 7.5.0) 解法, 执行用时: 2593ms, 内存消耗: 6016K, 提交时间: 2022-11-03 22:01:48

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx2","sse2","fma")
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll P = 1e9 + 7;
const int maxn = 1<<16;
const int N = 3e5 + 5;

ll a[N], val[N], n, t;

ll f[maxn][2];

void solve(){
    for(int i = 0 ; i < maxn ; i ++) f[i][0] = 1, f[i][1] = 0;

    ll x,k,p; cin >> x >> k >> p;

    vector<ll>fac;
    for(ll i = 2, tmp = p; tmp > 1 ; i ++){
        if(tmp%i != 0) continue;

        ll val = 1;
        while(tmp%i==0 && x%i==0) tmp/=i, x/=i,val *= i;
        while(tmp%i==0) tmp/=i;
        fac.push_back(val * i);
    }

    for(int i = 0 ; i < n ; i ++) val[i] = __gcd(a[i], p);
    for(int i = 0 ; i < n ; i ++){
        ll tmp = 0;
        for(int j = 0 ; j < (int)fac.size() ; j ++){
            if(val[i] % fac[j] != 0) tmp |= (1<<j);
        }

        f[tmp][1] = (f[tmp][1] * (k+1) + f[tmp][0]) % P;
        f[tmp][0] = f[tmp][0] * k % P;
    }

    int len = (1<<fac.size());

    for(int step = 1 ; step < len ; step *= 2){
        for(int i = 0 ; i < len ; i += 2*step){
            for(int j = i ; j < i + step ; j ++){
                ll l0 = f[j][0], l1 = f[j][1];
                ll r0 = f[j+step][0], r1 = f[j+step][1];

                f[j][0] = l0 * r0 % P;
                f[j][1] = l1 * r0 % P;
                f[j+step][0] = l0 * r0 % P;
                f[j+step][1] = (l0 * r1 + l1 * r0 + l1 * r1) % P;
            }
        }
    }

    int ans = 0;
    for(int i = 0 ; i < len ; i ++) {
        if((__builtin_popcount(i) + fac.size()) & 1) {
            (ans -= f[i][1]) < 0 ? ans += P: NULL;
        }
        else{
            (ans += f[i][1]) >= P ? ans -= P: NULL;
        }
    }

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> t;
    for(int i = 0 ; i < n ; i ++) cin >> a[i];

    while(t--){
        solve();
    }
}

C++(clang++11) 解法, 执行用时: 2826ms, 内存消耗: 2960K, 提交时间: 2020-11-27 21:53:13

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=3e5+5;
const int mod=1e9+7;
int n,T,K,p[15],q[15],f[1<<15|1];
long long a[N],X,P;
int fastpow(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return res;
}
void solve(){
	X=__gcd(X,P);
	int cnt=0;
	long long Q=P;
	for(int i=2;i<=300000;++i)
		if(Q%i==0){
			p[cnt++]=i;
			while(Q%i==0)
				Q/=i;
		}
	for(int i=0;i<cnt;++i){
		q[i]=0;
		while(X%p[i]==0)
			++q[i],X/=p[i];
	}
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;++i){
		long long tmp=__gcd(a[i],P);
		int mask=0;
		for(int j=0;j<cnt;++j){
			int t=0;
			while(tmp%p[j]==0)
				++t,tmp/=p[j];
			mask|=(t<=q[j])<<j;
		}
		++f[mask];
	}
	int all=(1<<cnt)-1;
	for(int j=1;j<=all;j<<=1)
		for(int i=0;i<=all;++i)
			if(i&j)
				f[i]+=f[i^j];
	int inv_k=fastpow(K,mod-2);
	for(int i=0;i<=all;++i)
		f[i]=fastpow(inv_k+1,f[i])-1;
	for(int j=1;j<=all;j<<=1)
		for(int i=0;i<=all;++i)
			if(i&j)
				f[i]=(f[i]-f[i^j]+mod)%mod;
	int ans=1ll*f[all]*fastpow(K,n)%mod;
	printf("%d\n",ans);
}
int main(){
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	while(T--){
		scanf("%lld%d%lld",&X,&K,&P);
		solve();
	}
	return 0;
}