| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4876 人关注过本帖
标题:【求助】杭电acm 1019 Least Common Multiple(最小公倍数)
只看楼主 加入收藏
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
收藏
得分:0 
回复 19楼 dreamofgod
这还不是用到了除法吗?没什么优势可言。

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-10-12 22:36
husiwen
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:227
专家分:1125
注 册:2010-5-23
收藏
得分:10 
return large * small / y;
改成large/y*small  关于代码优化问题,先乖数据可能超过int,会也错。。而且大数据运算。也容易超时
2011-10-12 22:48
husiwen
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:227
专家分:1125
注 册:2010-5-23
收藏
得分:0 
参考代码(1):
#include<stdio.h>
int lcm(int x,int y)
{
    int r = x , nx = x,ny = y;
    while(y != 0)
    {
        r = y;
        y = x%y;
        x = r;
    }
    return nx/x*ny;
}
int main()
{
    int m, n, i, re, T;
    scanf("%d", &T);
    while(T--)
{
        scanf("%d", &m);
        scanf("%d", &re);
        for(i = 1; i < m; i++)
{
            scanf("%d",&n);
            re = lcm(re,n);
        }
        printf("%d\n", re);
    }
    return 0;
}
参考代码(2):
#include<stdio.h>
int lcm(int x,int y){
    int r = x , nx = x,ny = y;
    while(y != 0)
    {
        r = y;
        y = x%y;
        x = r;
    }
    return nx*ny/x;
}
int main()
{
    int m, n, i, re, T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &m);
        scanf("%d", &re);
        for(i = 1; i < m; i++)
        {
            scanf("%d",&n);
            re = lcm(re,n);
        }
        printf("%d\n", re);
    }
    return 0;
}

特别提醒:
参考代码(2)与参考代码(1)有什么不同?我们发现,仅仅是计算最小公倍数的过程中,计算次序的不同。在数学中,两者完全相同,但是在这个题目中,参考代码(2)却是错误的。题目中已经给出所有输入数据以及结果,都在32位整数范围以内,使用int来计算。但是显然,a*b/d 这个数字在int以内,并不意味着a*b也在int以内。错误的原因就是中间结果溢出。
2011-10-12 22:53
快速回复:【求助】杭电acm 1019 Least Common Multiple(最小公倍数)
数据加载中...
 
   



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

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