菜鸡的题解011——Hankson的趣味题

被坑了好久（还是因为我太菜了）。。

说下我的思路历程，因为a1是x的约数，b1/b0也是x的约数，所以我找了a1和b1/b0的最小公倍数a，符合条件的x必定是a的倍数。

这个思路提交，时间超限73。

后来参考大佬写法，让i依次加一截至到i*i>b1，时间超限93.

最后发现因为用了longlong输入，改成int以后时间立马从两千四降到四百。

离谱离谱。。（以后都自己写read了）

参考代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
const int N=1<<10+1;
int n,a1,a0,b1,b0;
int gcd(int x,int y){
	return y==0?x:gcd(y,x%y);
}
int main(){
    cin>>n;
    while(n--){
    	scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
    	int cnt=0;
    	for(int i=1;i*i<=b1;i++){
    		if(b1%i!=0)continue;
    		if(gcd(a0,i)==a1&&b0*i==b1*gcd(b0,i)){
    			cnt++;
    		}
    		if((i*i)!=b1){
    			int x=b1/i;
    			if(gcd(a0,x)==a1&&b0*x==b1*gcd(b0,x)){
				    cnt++;
				}
			}
		}
		cout<<cnt<<endl;
	}
}