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;
}本回答被提问者采纳
