（以“分类:简单数学问题 {{信息题|最大公约数和最小公倍数问题|http://www.wikioi.com/problem/1012/|2|80|未知}} ==题意== 求以x0为最大公...”为内容创建页面） |
小 （表格格式） |
||
| 第5行： | 第5行： | ||
==题解== | ==题解== | ||
有两个数满足条件，那么把它们分解质因数，两边质因数取并集（有相同因子取最多）就是最小公倍数，取交集（相同因子取最少）就是最大公约数。 | 有两个数满足条件，那么把它们分解质因数，两边质因数取并集（有相同因子取最多）就是最小公倍数，取交集（相同因子取最少）就是最大公约数。 | ||
| − | |||
举个栗子： | 举个栗子： | ||
{| class="wikitable" | {| class="wikitable" | ||
| 第22行： | 第21行： | ||
|} | |} | ||
很显然，x0、y0相差的因子即最小公倍数除以最大公约数之商。把这些质因子分成两组就可以得到最终解。 | 很显然，x0、y0相差的因子即最小公倍数除以最大公约数之商。把这些质因子分成两组就可以得到最终解。 | ||
| − | |||
于是先求得<m>U=\frac{y0}{x0}</m>，然后把U分解质因数得到： | 于是先求得<m>U=\frac{y0}{x0}</m>，然后把U分解质因数得到： | ||
{| class="wikitable" | {| class="wikitable" | ||
| 第28行： | 第26行： | ||
! 质因子!! <m>a_1</m> !! <m>a_2</m> !! <m>a_3</m> !! ... !! <m>a_n</m> | ! 质因子!! <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> || ... | + | | 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>。 | 那么p、q可以以x0为初始值，再把质因子分给这些p、q乘上，得到一组p、q。每个质因子要么分给p，要么分给q，那么所有可能性很容易得到就是<m>2^n</m>。 | ||
| − | |||
所以问题就转化为求<m>U=\frac{y0}{x0}</m>的质因子数n了，然后输出<m>2^n</m>即可。 | 所以问题就转化为求<m>U=\frac{y0}{x0}</m>的质因子数n了，然后输出<m>2^n</m>即可。 | ||
| − | |||
什么你问我怎么写阶乘？2的次方好伐，直接用位运算左移(<<)1就好啦即： | 什么你问我怎么写阶乘？2的次方好伐，直接用位运算左移(<<)1就好啦即： | ||
<pre> | <pre> | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 最大公约数和最小公倍数问题 | ★★☆☆☆ | 答案错误 | 80 | {{{time}}} | 未知 |
求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。
有两个数满足条件，那么把它们分解质因数，两边质因数取并集（有相同因子取最多）就是最小公倍数，取交集（相同因子取最少）就是最大公约数。 举个栗子：
| 质因子 | 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相差的因子即最小公倍数除以最大公约数之商。把这些质因子分成两组就可以得到最终解。
于是先求得，然后把U分解质因数得到：
| 质因子 | |
|
|
... | |
|---|---|---|---|---|---|
| U | |
|
|
... | |
那么p、q可以以x0为初始值，再把质因子分给这些p、q乘上，得到一组p、q。每个质因子要么分给p，要么分给q，那么所有可能性很容易得到就是。
所以问题就转化为求的质因子数n了，然后输出
即可。
什么你问我怎么写阶乘？2的次方好伐，直接用位运算左移(<<)1就好啦即：
1<<n;
| 1012.cpp代码已折叠
展开折叠内容
|
|---|
#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;
}
|
CloudLunar