小 （表格格式） |
小 （完成题目） |
||
| 第1行： | 第1行： | ||
[[分类:简单数学问题]] | [[分类:简单数学问题]] | ||
| − | {{信息题|最大公约数和最小公倍数问题|http://www.wikioi.com/problem/1012/|2| | + | {{信息题|最大公约数和最小公倍数问题|http://www.wikioi.com/problem/1012/|2|100|无解情况|80}} |
==题意== | ==题意== | ||
求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。 | 求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。 | ||
| 第35行： | 第35行： | ||
1<<n; | 1<<n; | ||
</pre> | </pre> | ||
| + | ==错误分析== | ||
| + | 第一次WA80，后来发现居然第四个点y0%x0!=0，要无解情况特判（输出零），一定是太久没写题这种坑都忘记了。 | ||
==代码== | ==代码== | ||
{{折叠|1012.cpp代码已折叠 | {{折叠|1012.cpp代码已折叠 | ||
| 第49行： | 第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 | {{{time}}} | 无解情况（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