description
今有一序列,名之曰(num),其长为(n).另有一数,其值为(p).求(n)中满足(a_{i}*a_{j}*a_{k})为(p)的倍数.
solution
果然没思路的题就是(dp).(60)分很水,(Omicron(nsqrt{p}+n^{2}))的算法也很好想,下面在此算法基础上,直接讨论正解.
在暴力的基础上,我们考虑将一一枚举转化为状态转移.设(f[i][j])表示选用了(i)个数所能达到与(p)的最大公约数为(j)的方案数,于是乎,我们可以一一枚举(num_{i}),倒序枚举(j),然后再一一枚举(p)的约数进行递推即可,这里倒叙枚举(j),是为了防止同一个(num_{i})重复统计贡献.算法复杂度上界(Omicron(3ncdot sqrt{p}))
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define R register
#define next kdjadskfj
#define debug puts("mlg")
#define mod 10007
#define Mod(x) ((x%mod+mod)%mod)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writeln(ll x);
inline void writesp(ll x);
ll n,p,ans;
ll num[310000],num1[310000];
ll rem[1100000];
ll c[1100],h;
ll pos[1100000];
ll f[4][1200];
inline ll gcd(ll _,ll __){ll ___;while(__!=0){___=_%__;_=__;__=___;}return _;}
inline ll calc1(ll x){return p/gcd(p,x);}
inline ll calc2(ll x,ll y){ll t=p;t/=gcd(t,x);t/=gcd(t,y);return t;}
inline ll calc3(ll x,ll y,ll z){ll t=p;t/=gcd(t,x);t/=gcd(t,y);t/=gcd(t,z);return t;}
inline bool check(ll x,ll y,ll z){return calc3(x,y,z)==1;}
inline void solve1();
inline void solve2();
inline void solve3();
int main(){
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
n=read();p=read();
for(R ll i=1;i<=n;i++) num[i]=read();
if(n<=100) solve1();
if(n<=2000)solve2();
solve3();
}
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}
inline void solve1(){
for(R ll i=1;i<=n;i++){
for(R ll j=i+1;j<=n;j++){
for(R ll k=j+1;k<=n;k++){
if(check(num[i],num[j],num[k])) ++ans;
}
}
}
writeln(ans);
exit(0);
}
inline void solve2(){
for(R ll i=1;i<=n;i++){
num1[i]=gcd(num[i],p);
for(R ll j=1;j*j<=num1[i];j++){
if(num1[i]%j==0){
if(j*j==num1[i]) ++rem[j];
else ++rem[j],++rem[num1[i]/j];
}
}
}
for(R ll i=1,num2;i<=n;i++){
for(R ll j=i+1;j<=n;j++){
num2=calc2(num[i],num[j]);
ans+=rem[num2];
if(num1[i]%num2==0) --ans;
if(num1[j]%num2==0) --ans;
}
}
writeln(ans/3);
exit(0);
}
inline void solve3(){
for(R ll i=1;i<=n;i++) num1[i]=gcd(num[i],p);
for(R ll i=1;i*i<=p;i++){
if(i*i==p) c[++h]=i;
else if(p%i==0) c[++h]=i,c[++h]=p/i;
}
for(R ll i=1;i<=h;i++) pos[c[i]]=i;
for(R ll i=1;i<=n;i++){
for(R ll j=3;j>=1;j--){
if(j==1){
++f[1][pos[num1[i]]];
continue;
}
else{
for(R ll k=1;k<=h;k++){
if(!f[j-1][k]) continue;
f[j][pos[gcd(num1[i]*c[k],p)]]+=f[j-1][k];
}
}
}
}
writeln(f[3][pos[p]]);
}