P1072 [NOIP2009 提高组] Hankson 的趣味题题解
description
there
solution
我们令集合 P 为将 b_{1} 质因数分解后所能组成的数的集合。
根据最大公因数和最小公倍数的性质容易发现 answer \in P。
那我们就可以将集合 P 中的数挨个 check 看是否满足：
-
-
时间复杂度计算
对于任意一个数 p 都可以拆成如下形式：
其中 $a_1,a_2...a_n$ 为质数， $b_1,b_2...b_n \in \mathbb N*$。
用 $p$ 的质因数组合的情况数为 $(b_1 + 1) \cdot (b_2 + 1) \cdot ... \cdot (b_n + 1) $。
不难得到 在最坏情况下 $a$ 数组为 $\set{2, 3, 5, 7 ...}$。
经验证，当到 $a_{11}$ 时，总和会爆 int。
所以在最坏情况下，有 $2^{10}$ 种情况，不会爆炸。
~~注：本题解来自机房某[大佬](https://www.luogu.com.cn/user/1308003)，本蒟蒻只是借鉴。~~
## code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1145;
int tot=0,ans=0;
int a0,a1,b0,b1,B1,a[N];
int top;
int lcm(int a,int b){
return (a/__gcd(a,b)*b);
}
struct node{
int val,num;
};
vector<node> pri;
bool check(int x){
if(__gcd(x,a0)==a1 && lcm(x,b0)==b1) return 1;
return 0;
}
void dfs(int x,int sum){
if(x==tot){
if(check(sum))ans++;
return;
}
for(int i=0;i<=pri[x].num;i++)
dfs(x+1, pow(pri[x].val,i)*sum);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
top=0;
cin>>a0>>a1>>b0>>b1;
B1=b1;
pri.clear();
memset(a,0,sizeof(a));
for(int i=2;i<=sqrt(b1);i++){
while(B1%i==0){
B1/=i;
a[++top]=i;
}
}
if(B1!=1) a[++top]=B1;
int res=0;
for(int i=1;i<=top+1;i++){
if(a[i]!=a[i-1]){
pri.push_back({a[i-1],res});
res=1,tot++;
}
else res++;
}
tot = pri.size();
if (tot == 0) tot = 1;
ans=0;
dfs(1,1);
cout<<ans<<endl;
}
}
```