AcWing 200. Hankson的趣味题
原题链接
中等
作者:
上班摸鱼中
,
2023-03-28 11:14:54
,
所有人可见
,
阅读 102
//1-n中的质数个数为n/ln(n)
//45000/ln(45000)=20
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
//(2x10^9)1/2=45000
const int N=45000,M=50;
int primes[N],cnt;
bool st[N];
PII factor[M];
int cntf;
int res;
void get_primes(int n) // 线性筛质数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int divider[N],cntd;
void dfs(int u,int p)
{
if(u>=cntf)
{
divider[cntd++] = p;
return;
}
for(int i=0;i<=factor[u].second;i++)
{
dfs(u+1,p);
p*=factor[u].first;
}
}
int gcd(int a, int b) // 欧几里得算法
{
return b ? gcd(b, a % b) : a;
}
int main()
{
//先把45000以内的质数表都打印出来
get_primes(N-1);
int n;
cin>>n;
while (n -- )
{
res=0;
int a0,a1,b0,b1;
cin>>a0>>a1>>b0>>b1;
int d=b1;
cntf=0;
//拆成质因数分解的样式
for(int i=0;primes[i]<=d/primes[i];i++)
{
if(d%primes[i]==0)
{
//记录有几个primes[i]
int s=0;
while(d%primes[i]==0)
{
s++;
d/=primes[i];
}
factor[cntf++]={primes[i],s};
}
}
if(d>1) factor[cntf++]={d,1};
//至此,全部分解成素数相乘
//爆搜存储d的所有约数
cntd = 0;
dfs(0,1);
for(int i=0;i<cntd;i++)
{
int x = divider[i];
if(gcd(x,a0)==a1 && (LL)x*b0/gcd(x,b0)==b1)
res++;
}
cout<<res<<endl;
}
return 0;
}