题解:P1072 [NOIP2009 提高组] Hankson 的趣味题

· · 题解

题意

求满足 gcd (x,a_0)=a_1, lcm (x,b_0)=b_1x 个数。

思路

## Code ```cpp #include <bits/stdc++.h> #define int long long #define fro for using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen (".in","r",stdin); //freopen (".out","w",stdout); int n; cin>>n; while (n--) { int a,aa,b,bb; cin>>a>>aa>>b>>bb; int sum=0; for (int i=1;i*i<=bb;i++) { if (bb%i==0) { int other=bb/i; if (b*i/__gcd(b,i)==bb&&__gcd(i,a)==aa) sum++; if (other!=i/*另一个因数与i不同*/&&b*other/__gcd(b,other)==bb&&__gcd(a,other)==aa) sum++; } } cout<<sum<<endl; } return 0; } ```