Problem B:有限小数
Time Limit:1000MS Memory Limit:65536K
Total Submit:78 Accepted:18
Description
mg最近对分数产生了兴趣,大家都知道,任何一个有限小数都可以换成分数的形式,mg在想,是不是任何的分数也可以都能换成有限小数呢?答案是不一定的,如:1/4=0.25而1/3=0.3333333………。所以mg现在想让你告诉他对一个分数m/n,是不是有限小数。
Input
输入有多组测试数据,每组测试数据包含两个整数m,n(m,n都在int范围内)。
当m,n同时为0时输入结束。
Output
对应的每组输入,如果m/n是有限小数输出yes,否则输出no。
Sample Input
1 2
2 3
0 0
Sample Output
yes
no
我自己也编了个,答案虽然对的上,但是时间超过了。
说个大体思路吧。
分数可化为有限小数,则分母跟分子约去相同因数后,分母只含有2跟5两个质因数。按照这个方法,我们可总结如下:
1.将分母化简,一直除2和5,直到分母等1或者分母不再能被2和5整除为止。记余数为X。
2.若X等于1,该分数一定可化为有限小数。
3.若X不等于1,分子除以X,若能除尽,则可化为有限小数,否则不是有限小数。
ps:判断能否被整除,可以用求余运算实现,余数为0,则能整除,否则不能整除。
分数可化为有限小数,则分母跟分子约去相同因数后,分母只含有2跟5两个质因数。按照这个方法,我们可总结如下:
1.将分母化简,一直除2和5,直到分母等1或者分母不再能被2和5整除为止。记余数为X。
2.若X等于1,该分数一定可化为有限小数。
3.若X不等于1,分子除以X,若能除尽,则可化为有限小数,否则不是有限小数。
ps:判断能否被整除,可以用求余运算实现,余数为0,则能整除,否则不能整除。
温馨提示:答案为网友推荐,仅供参考
第1个回答 2010-03-07
#include <stdio.h>
int maxdivisor(int m, int n)
{
int r;
while (m % n) {
r = m%n;
m = n;
n = r;
}
return n;
}
int main()
{
int m, n;
int div;
while (scanf("%d%d", &m, &n), m+n) {
div = maxdivisor(m, n);
m /= div;
n /= div;
while (n%5 == 0)
n /=5;
while (n%2 == 0)
n /= 2;
if (n > 2)
puts("no");
else
puts("yes");
}
return 0;
}本回答被提问者采纳
int maxdivisor(int m, int n)
{
int r;
while (m % n) {
r = m%n;
m = n;
n = r;
}
return n;
}
int main()
{
int m, n;
int div;
while (scanf("%d%d", &m, &n), m+n) {
div = maxdivisor(m, n);
m /= div;
n /= div;
while (n%5 == 0)
n /=5;
while (n%2 == 0)
n /= 2;
if (n > 2)
puts("no");
else
puts("yes");
}
return 0;
}本回答被提问者采纳