| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4876 人关注过本帖
标题:【求助】杭电acm 1019 Least Common Multiple(最小公倍数)
只看楼主 加入收藏
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
楼主的问题应该出在,return large * small / y;这句上。
先进行乘法运算可能造成溢出。
调换一下运算顺序,先做除法运算。

重剑无锋,大巧不工
2011-10-07 00:42
『点点滴滴』
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:168
专家分:1035
注 册:2007-7-9
收藏
得分:10 
#include <stdio.h>
int gcd( int a , int b )
{
    return b == 0 ? a : gcd( b , a % b ) ;
}
int main()
{
    int Total , n , x , s ;
    scanf("%d", &Total ) ;
    while( Total-- )
    {
        s = 1 ;
        scanf("%d", &n ) ;
        while( n-- )
        {
            scanf("%d", &x ) ;
            s = s / gcd( s , x ) * x ;
        }
        printf("%d\n", s ) ;
    }
    return 0 ;
}
程序代码:
#include <stdio.h>

int fun (int x, int y)            //求两数的最小公倍数
{
    int        temp, r, large, small;

    if (x < y)
    {
        temp = y;
        y     = x;
        x     = temp;
    }
    large = x;
    small = y;
    while ((r = x % y) > 0)
    {
        x = y;
        y = r;
    }

    return large / y * small ;
}
int    main ()
{
    int        m, n;
    int        i;
    int        a, mul;

    scanf ("%d", &m);
    while (m--)
    {
        scanf ("%d", &n);
        mul = 1;
        for (i = 0; i < n; i++)
        {
            scanf ("%d", &a);
            mul = fun (mul, a);
        }
        printf ("%d\n", mul);
    }

    return 0;
}




[ 本帖最后由 『点点滴滴』 于 2011-10-7 08:31 编辑 ]
2011-10-07 08:28
落叶深蓝色
Rank: 8Rank: 8
来 自:山东
等 级:蝙蝠侠
帖 子:319
专家分:807
注 册:2010-12-8
收藏
得分:10 
接分,
2011-10-07 13:21
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:0 
回复 11楼 beyondyf
是这样啊,没想那么多,怪不得不对。

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-10-09 21:56
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:0 
回复 9楼 wxfcyuyan
很遗憾,这是在做题,输出必须和它给的示例一模一样,而且单纯这样改也不能通过测试。

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-10-09 21:59
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:0 
回复 4楼 草狼
我明白了,里面的数先相乘可能会变成非常大的数,这样就会导致精度损失,在/y的数就不对了,
用长整型后就不会导致精度损失了,而且/y之后的数值即使由int型去表示也不会损失精度,但是还有一个问题,为什么我把函数返回值类型也变成long long之后还是会出错呢?

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-10-09 22:03
dreamofgod
Rank: 5Rank: 5
等 级:职业侠客
帖 子:194
专家分:341
注 册:2011-8-16
收藏
得分:10 
除法可能有精度问题。
改用减法如何?不断的减,结果为0则整除,结果直接小于0则不能整除……

一个单片机就让我头疼不已~~~
2011-10-10 21:55
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:0 
回复 17楼 dreamofgod
这样执行循环的时间会不会太长,尤其是减数比较小的时候?

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-10-10 22:22
dreamofgod
Rank: 5Rank: 5
等 级:职业侠客
帖 子:194
专家分:341
注 册:2011-8-16
收藏
得分:0 
回复 18楼 waterstar
先一次性减至接近值。
比如10001/2,10001-取整(10001/2-1)*2,反正速度和直接除是没得比了……

一个单片机就让我头疼不已~~~
2011-10-11 15:06
fedcab123
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:168
专家分:100
注 册:2011-9-3
收藏
得分:10 
看不懂
2011-10-11 15:14
快速回复:【求助】杭电acm 1019 Least Common Multiple(最小公倍数)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.083692 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved