最大公因数和最小公倍数与素数分解式有什么联系呢?
举例说明:
对于12 = 2(2) * 3(1) * 5(0);
对于15 = 2(0) * 3(1) * 5(1);
最大公倍数:2(0) * 3(1) * 5(0);
最小公因数:2(2) * 3(1) * 5(1);
综上可知:
$\color{#FF0000}{将两个数素数分解式中每个素因子的指数部分取两个中的最小值,就得到了两个数的最大公因数}$
$\color{#FF0000}{将两个数素数分解式中每个素因子的指数部分取两个中的最大值,就得到了两个数的最小公倍数}$
#include <iostream>
#include <cmath>
using namespace std;
int devide(int n)
{
int cnt = 0;
for (int i = 2; i <= n / i; i ++ )
{
if (n % i == 0)
{
cnt ++;
while (n % i == 0) n /= i;
}
}
if (n > 1) cnt ++;
return cnt;
}
int main()
{
int n, m;
cin >> n >> m;
if (m % n) cout << 0 << endl;
else cout << (1 << devide(m / n)) << endl;
return 0;
}