记录编号	556221	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]Hankson的趣味题	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	1.479 s
提交时间	2020-10-18 11:26:48	内存使用	8.54 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define LL long long
using namespace std;
const int maxN = 4e5 + 10;

void factor(LL n);
void primes(int n);
LL lcm(LL a, LL b);
LL gcd(LL a, LL b);

int n, m;
LL fac[maxN];
bool v[maxN];
int main(void){
	freopen("son.in","r",stdin);
	freopen("son.out","w",stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++){
		LL a0, a1, b0, b1;
		int ans = 0;
		scanf("%lld%lld%lld%lld", &a0, &a1, &b0, &b1);
		factor(b1);
		for (int i = 1; i <= m; i ++){
			if (gcd(a0, fac[i]) == a1 && lcm(fac[i], b0) == b1)
				ans ++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

LL gcd(LL a, LL b){
	return b ? gcd(b, a % b) : a;
}

LL lcm(LL a, LL b){
	return (a * b) / gcd(a, b);
}

void factor(LL n){
	m = 0;
	for (int i = 1; i * i <= n; i ++){
		if (n % i == 0){
			fac[++ m] = i;
			if (i != n / i)
				fac[++ m] = n / i;
		}
	}
}