洛谷 P1072 Hankson 的趣味题 解题报告

时间:2024-09-09 18:04:38

P1072 \(Hankson\)的趣味题

题目大意:已知有\(n\)组\(a0,a1,b0,b1\),求满足\((x,a0)=a1\),\([x,b0]=b1\)的\(x\)的个数。

数据范围:\(1<=n<=2,000,a0,a1,b0,a1<=2*1e9\)


用不是特别快的方法水过去的。

暴力枚举\(b1\)的约数,代入检验。

普通枚举约数复杂度\(O(\sqrt(L))\),检验的复杂度\(O(logL)\)。

考虑到约数一个数\(k\)约数个数期望是\(log\)的。

所以先筛一遍质数,把\(b1\)分解质因数,然后用DFS跑出\(b1\)的所有约数,复杂度\(O(logn)\)

总体复杂度\(O(nlog^2L)\)


Code:

#include <cstdio>
#include <cmath>
const int N=50000;
int pri[N+10],v[N+10],is_pri[N+10],cnt;
void init()
{
for(int i=2;i<=N;i++)
{
if(!is_pri[i])
{
pri[++cnt]=i;
v[i]=i;
}
for(int j=1;j<=cnt&&pri[j]*i<=N;j++)
{
if(v[i]<pri[j]) break;
is_pri[i*pri[j]]=1;
v[i*pri[j]]=pri[j];
}
}
}
int d[N][2],cnt0=0;
void get(int a)
{
for(int i=1;i<=cnt&&a>=pri[i];i++)
{
if(a%pri[i]==0)
{
cnt0++;
d[cnt0][1]=pri[i];
d[cnt0][0]=0;
while(a%pri[i]==0)
{
d[cnt0][0]++;
a/=pri[i];
}
}
}
if(a>1) {d[++cnt0][1]=a;d[cnt0][0]=1;}
}
int f[N],cntt=0;
void dfs(int dep,int now)
{
if(dep==cnt0+1)
{
f[++cntt]=now;
return;
}
dfs(dep+1,now);
for(int i=1;i<=d[dep][0];i++)
{
now*=d[dep][1];
dfs(dep+1,now);
}
}
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
void work()
{
int a0,a1,b0,b1,ans=0;
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
cnt0=0,cntt=0;
get(b1);
dfs(1,1);
for(int i=1;i<=cntt;i++)
{
int k1=gcd(f[i],b0),k2=gcd(f[i],a0);
if(k1*b1==f[i]*b0&&k2==a1)
ans++;
}
printf("%d\n",ans);
}
int main()
{
int n;init();
scanf("%d",&n);
while(n--)
work();
return 0;
}

2018.7.4