（以“分类:简单数学问题 {{信息题|最大公约数和最小公倍数问题|http://www.wikioi.com/problem/1012/|2|80|未知}} ==题意== 求以x0为最大公...”为内容创建页面） |
小 （date） |
||
| （未显示1个用户的5个中间版本） | |||
| 第1行： | 第1行： | ||
[[分类:简单数学问题]] | [[分类:简单数学问题]] | ||
| − | {{信息题|最大公约数和最小公倍数问题|http://www. | + | {{信息题|最大公约数和最小公倍数问题|http://www.codevs.cn/problem/1012/|2|100|无解情况|80|time=2014/08/17 23:01:06}} |
==题意== | ==题意== | ||
求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。 | 求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。 | ||
==题解== | ==题解== | ||
有两个数满足条件，那么把它们分解质因数，两边质因数取并集（有相同因子取最多）就是最小公倍数，取交集（相同因子取最少）就是最大公约数。 | 有两个数满足条件，那么把它们分解质因数，两边质因数取并集（有相同因子取最多）就是最小公倍数，取交集（相同因子取最少）就是最大公约数。 | ||
| − | |||
举个栗子： | 举个栗子： | ||
{| 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> | ||
1<<n; | 1<<n; | ||
</pre> | </pre> | ||
| + | ==错误分析== | ||
| + | 第一次WA80，后来发现居然第四个点y0%x0!=0，要无解情况特判（输出零），一定是太久没写题这种坑都忘记了。 | ||
==代码== | ==代码== | ||
{{折叠|1012.cpp代码已折叠 | {{折叠|1012.cpp代码已折叠 | ||
| 第53行： | 第51行： | ||
scanf("%d%d",&x0,&y0); | scanf("%d%d",&x0,&y0); | ||
U=y0/x0; | U=y0/x0; | ||
| + | if(y0%x0){ | ||
| + | printf("0"); | ||
| + | return 0; | ||
| + | } | ||
for(int i=2;i<=U;++i)//分解质因数 | for(int i=2;i<=U;++i)//分解质因数 | ||
if(!(U%i)) | if(!(U%i)) | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 最大公约数和最小公倍数问题 | ★★☆☆☆ | 答案正确 | 100 | 2014/08/17 23:01:06 | 无解情况（80） |
求以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;
第一次WA80，后来发现居然第四个点y0%x0!=0，要无解情况特判（输出零），一定是太久没写题这种坑都忘记了。
| 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;
if(y0%x0){
printf("0");
return 0;
}
for(int i=2;i<=U;++i)//分解质因数
if(!(U%i))
if(t(i))
++n;
printf("%lld",1<<(long long int)n);
return 0;
}
|
CloudLunar