[CodeVS 1012]最大公约数和最小公倍数问题
转载请注明出处：http://danihao123.is-programmer.com/
很经典的问题了吧……然而现在才A……
应注意[tex]P*Q=x*y[/tex]，然而[tex]P[/tex]和[tex]Q[/tex]都可表示为[tex]x[/tex]的乘积，问题就好思考多了。答案就是[tex]y/x[/tex]的质因子的子集数（同一种质因子不能同时分配到P与Q中，否则gcd(P,Q)会不等于x）。
注意有可能无解！
代码：
#include <iostream>
using namespace std;
inline int fj(int x){
register int i,ans=0;
for(i=2;i<=x && x>1;i++)
if(!(x%i)){
ans++;
while(!(x%i))
x/=i;
}
return ans;
}
int main(){
int a,b;
register int ans;
cin>>a>>b;
if(b%a)
ans=0;
else
ans=a==1?1:1<<fj(b/a);
cout<<ans<<endl;
return 0;
}
Jul 02, 2023 11:53:57 AM
News coverage of current events across the nation. Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are committed about delivering education updates in emodelpaper.in the public interest while maintaining transparency.is a project of professional journalists who have gathered for specialised news coverage of current events across the nation Our team is made up of professional writers and citizen journalists.