danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26240

[CodeVS 1012]最大公约数和最小公倍数问题

2016年8月03日 18:34 | Comments(0) | Category:题解 | Tags:

很经典的问题了吧……然而现在才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;
}