Hankson的趣味题
算法
时间复杂度$O(n\sqrt{b1}\lg{k2})\thickapprox10^8$
很极限,反正过了~
算法描述
用了gcd和约数
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e8;
int a[N],cnt;
int T;
int gcd(int a,int b)
{
return b ? gcd(b,a % b): a;
}
int main()
{
cin >> T;
while(T --)
{
cnt = 0;
int a0,a1,b0,b1;
cin >> a0 >> a1 >> b0 >> b1;
int k2 = b1 / b0;
for(int i = 1;i * i <= b1;i ++)
{
if(b1 % i == 0)
{
int k1 = b1 / i;
if(gcd(k1,k2) == 1)a[cnt ++] = i;
if(i * i != b1 && gcd(i,k2) == 1)a[cnt ++] = b1 / i;
}
}
int res = 0;
for(int i =0 ;i < cnt ;i ++)
{
if(gcd(a[i],a0) == a1)res ++;
}
cout << res << endl;
}
}