小 （云璟月移动WikiOI/1012页面至CodeVS/1012，不留重定向：替换文字 - 「WikiOI」替换为「CodeVS」） |
小 （date） |
||
| 第1行： | 第1行： | ||
[[分类:简单数学问题]] | [[分类:简单数学问题]] | ||
| − | {{信息题|最大公约数和最小公倍数问题|http://www.codevs.cn/problem/1012/|2|100|无解情况|80}} | + | {{信息题|最大公约数和最小公倍数问题|http://www.codevs.cn/problem/1012/|2|100|无解情况|80|time=2014/08/17 23:01:06}} |
==题意== | ==题意== | ||
求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。 | 求以x0为最大公约数,以y0为最小公倍数的两个正整数p、q所有可能总数。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 最大公约数和最小公倍数问题 | ★★☆☆☆ | 答案正确 | 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