查看CodeVS/1012的源代码 ←CodeVS/1012

[[分类:简单数学问题]]
{{信息题|最大公约数和最小公倍数问题|http://www.wikioi.com/problem/1012/|2|80|未知}}
==题意==
求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。
==题解==
有两个数满足条件，那么把它们分解质因数，两边质因数取并集（有相同因子取最多）就是最小公倍数，取交集（相同因子取最少）就是最大公约数。
举个栗子：
{| class="wikitable"
|-
! 质因子!! 2 !! 3 !! 5
|-
| p=24 || 3 || 1 || 0
|-
| q=60 || 2 || 1 || 1
|-
| x0=12 || 2 || 1 || 0
|-
| y0=120 || 3|| 1 || 1
|-
| x0、y0相差的质因子 || 1 || 0 || 1
|}
很显然，x0、y0相差的因子即最小公倍数除以最大公约数之商。把这些质因子分成两组就可以得到最终解。
于是先求得<m>U=\frac{y0}{x0}</m>，然后把U分解质因数得到：
{| class="wikitable"
|-
! 质因子!! <m>a_1</m> !! <m>a_2</m> !! <m>a_3</m> !! ... !! <m>a_n</m>
|-
| U || <m>m_1</m> || <m>m_2</m> || <m>m_2</m> || ... || <m>m_n</m>
|}
那么p、q可以以x0为初始值，再把质因子分给这些p、q乘上，得到一组p、q。每个质因子要么分给p，要么分给q，那么所有可能性很容易得到就是<m>2^n</m>。

所以问题就转化为求<m>U=\frac{y0}{x0}</m>的质因子数n了，然后输出<m>2^n</m>即可。
什么你问我怎么写阶乘？2的次方好伐，直接用位运算左移(<<)1就好啦即：
<pre>
  1<<n;
</pre>
==代码==
{{折叠|1012.cpp代码已折叠
|<pre>
#include<cstdio>
bool t(int u){//判断i是否为素数
   for(int i=2;i*i<=u;++i)
    if(u%i==0)
      return 0;
   return 1;
}
int main(){
  int x0,y0,U,n=0;
  scanf("%d%d",&x0,&y0);
  U=y0/x0;
  for(int i=2;i<=U;++i)//分解质因数
    if(!(U%i))
      if(t(i))
        ++n;
  printf("%lld",1<<(long long int)n);
  return 0;
}
</pre>
|code1012}}