题意:
有n个询问,在每个询问中,先给定四个自然数a,b,c,d,然后求出有多少个x满足\( gcd(a,x)=b\) 并且\(lcm(c,x)=d\). 数据范围:\(n<=2000,1<=a,b,c,d<=2*10^9\).
Solution:
这道题有多种办法:题解
一开始尝试暴力解法,枚举d的约数,然后直接判断是否符合题目的两个条件,最后一组数据果然超时了.然后书上还有通过质因子构造约数的方法,还未尝试过.在网上看题解时发现暴力解法还可以优化,主要是要想到下面这条性质来加速GCD运算:
对两个正整数\(a,b\),设 \(gcd(a,b)=k\),则有 \(gcd(a/k,b/k)=1\).
明天写一下其他思路. 还是太菜了啊,抓紧学习啊!
暴力优化法:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
#define MAX_N 2e9
typedef long long ll;
typedef unsigned long long ull;
int gcd(int a, int b) {
if (b) return gcd(b, a % b);
return a;
}
int main() {
int n;
cin >> n;
while (n--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int ans = 0;
for (int i = 1; i*i <= d; i++) {
if(d%i==0){
if (i%b==0&&gcd(a/b, i/b) == 1&& gcd(d/i,d/c)==1) {
ans++;
}
int j=d/i;
if(j!=i){
if(j%b==0&&gcd(a/b,j/b)==1&& gcd(d/j,d/c)==1){
ans++;
}
}
}
}
cout<<ans<<endl;
}
return 0;
}