[NOIP 2009 提高组] Hankson 的趣味题

知识点

质因数分解、最大公约数、最小公倍数

解题思路

由lcm(x,b0)=b1可知x必须整除b1。分解b1，对每个质数p，枚举x中指数e从0到b1指数E，检查min(e,vp(a0))=vp(a1)、max(e,vp(b0))=E，统计可行e个数并相乘。若a1不整除b1先输出0。用筛出的素数加速分解。

正确性说明

gcd和lcm的质因数指数分别为最小值和最大值，所以每个p上的两个条件恰与枚举判定相同。x只含b1中的质因数；a0中其他因数只能与x产生0指数，a1整除b1保证它们不造成遗漏。不同质数指数可独立组合，由乘法原理得总方案。

易错点

输入虽保证a0%a1=0、b1%b0=0，仍可能无解；b1=1时分解为空且答案由a1是否为1决定；不能把公倍数条件误作整除。

复杂度

筛素数O(U log log U)，每组分解约O(π(√b1))，指数检查很少；U=44722。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);vector<int>pr;vector<bool>bad(44723);for(int i=2;i<=44722;i++)if(!bad[i]){pr.push_back(i);if(1LL*i*i<=44722)for(int j=i*i;j<=44722;j+=i)bad[j]=true;}int T;cin>>T;while(T--){long long a0,a1,b0,b1;cin>>a0>>a1>>b0>>b1;if(b1%a1){cout<<0<<'\n';continue;}long long x=b1;vector<pair<long long,int>>f;for(int p:pr){if(1LL*p*p>x)break;if(x%p==0){int e=0;while(x%p==0)x/=p,e++;f.push_back({p,e});}}if(x>1)f.push_back({x,1});auto val=[](long long a,long long p){int e=0;while(a%p==0)a/=p,e++;return e;};long long ans=1;for(auto [p,E]:f){int A=val(a0,p),B=val(a1,p),C=val(b0,p),ways=0;for(int e=0;e<=E;e++)ways+=min(e,A)==B&&max(e,C)==E;ans*=ways;}cout<<ans<<'\n';}}