codeVS 1172 Hankson 的趣味题

枚举。

为什么要写这道题的题解呢，因为这道题有小技巧。

1.首先由题意知b1%x==0，这个条件如何用呢，就是x从1到sqrt（b1)枚举，其他符合条件的数肯定是b1/x中的一部分。

2.枚举条件不要直接写sqrt(b1)否则每回都会计算一遍，会tle。应该用i^2<=b1或者事先计算m=(int)sqrt(n+0.5)。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

inline int gcd(int a,int b) {
    return b==0? a : gcd(b,a%b);
}

int a0,a1,b0,b1,n,x,j,m;

bool check(int x) {
    if(x%a1!=0) return false;
    return gcd(x,a0)==a1 && gcd(b1/x,b1/b0)==1;
}

int main() {
    scanf("%d",&n);
    while(n--) {
        x=0;
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        for(int i=1;i*i<=b1;i++) 
            if(b1%i==0) {
                if(check(i)) x++;
                j=b1/i;
                if(j!=i) if(b1%j==0 && check(j)) x++;
            }
        printf("%d
",x);
    }
    return 0;
}