#1192: 還有更快的算法嗎??


B88000005 (喔~~!!XD)

學校 : 國立內壢高級中學
編號 : 4538
來源 : [118.167.234.168]
最後登入時間 :
2021-05-12 14:50:32
d101. 最小公倍數 | From: [220.138.34.169] | 發表日期 : 2009-01-18 18:16

這題因為是很多個數字的最小公倍數,

所以好像不能使用輾轉相除法??

所以我用了先把前面乘起來之後跟下一個數字的關係,

以下是我的式子:

#include <iostream>
#include <string>
#include <sstream>

using namespace std;
int c=0,q=0;
int GCD(int o,int p){
    while(p>0){
        c=o%p;
        o=p;
        p=c;
    }
    q=o;
}
int main()
{
    string x;
    stringstream X;
    while(getline(cin,x)){
        X.clear();
        X.str(x);
        int n=0;
        long long m=1;
        while(X>>n){
            if(n==0){
                return 0;
            }
            GCD(m,n);
            if(q==1){
                m*=n;
            }
            else{
                m=m*n/q;
            }
        }
        cout<<m<<endl;
    }
    return 0;
}

可是還是會超過1S耶??

最快的好像超過兩百微秒??

這題的時間可不可以再長一點ˊˋ? 
#1199: Re:還有更快的算法嗎??


magrady (元元)

學校 : 臺北市立第一女子高級中學
編號 : 1445
來源 : [114.34.203.11]
最後登入時間 :
2024-01-15 00:19:19
d101. 最小公倍數 | From: [218.164.217.134] | 發表日期 : 2009-01-18 19:45

這題因為是很多個數字的最小公倍數,

所以好像不能使用輾轉相除法??

所以我用了先把前面乘起來之後跟下一個數字的關係,

以下是我的式子:

#include
#include
#include

using namespace std;
int c=0,q=0;
int GCD(int o,int p){
    while(p>0){
        c=o%p;
        o=p;
        p=c;
    }
    q=o;
}
int main()
{
    string x;
    stringstream X;
    while(getline(cin,x)){
        X.clear();
        X.str(x);
        int n=0;
        long long m=1;
        while(X>>n){
            if(n==0){
                return 0;
            }
            GCD(m,n);
            if(q==1){
                m*=n;
            }
            else{
                m=m*n/q;
            }
        }
        cout<<
    }
    return 0;
}

可是還是會超過1S耶??

最快的好像超過兩百微秒??

這題的時間可不可以再長一點ˊˋ?

這題主要是在考快速輸出入的技巧.

稍微看了一下,演算法應該是能AC的. 

 
#1200: Re:還有更快的算法嗎??


magrady (元元)

學校 : 臺北市立第一女子高級中學
編號 : 1445
來源 : [114.34.203.11]
最後登入時間 :
2024-01-15 00:19:19
d101. 最小公倍數 | From: [218.164.217.134] | 發表日期 : 2009-01-18 19:48

這題因為是很多個數字的最小公倍數,

所以好像不能使用輾轉相除法??

所以我用了先把前面乘起來之後跟下一個數字的關係,

以下是我的式子:

#include
#include
#include

using namespace std;
int c=0,q=0;
int GCD(int o,int p){
    while(p>0){
        c=o%p;
        o=p;
        p=c;
    }
    q=o;
}
int main()
{
    string x;
    stringstream X;
    while(getline(cin,x)){
        X.clear();
        X.str(x);
        int n=0;
        long long m=1;
        while(X>>n){
            if(n==0){
                return 0;
            }
            GCD(m,n);
            if(q==1){
                m*=n;
            }
            else{
                m=m*n/q;
            }
        }
        cout<<
    }
    return 0;
}

可是還是會超過1S耶??

最快的好像超過兩百微秒??

這題的時間可不可以再長一點ˊˋ?

這題主要是在考快速輸出入的技巧.

稍微看了一下,演算法應該是能AC的. 


我ReJudge後還是WA. 
#1251: Re:還有更快的算法嗎??


gene91 (Gene JHZ)

學校 : 华东师范大学第二附属中学
編號 : 4272
來源 : [50.76.52.231]
最後登入時間 :
2012-07-10 13:27:34
d101. 最小公倍數 | From: [58.247.167.195] | 發表日期 : 2009-01-24 21:10

這題因為是很多個數字的最小公倍數,

所以好像不能使用輾轉相除法??

所以我用了先把前面乘起來之後跟下一個數字的關係,

以下是我的式子:

#include
#include
#include

using namespace std;
int c=0,q=0;
int GCD(int o,int p){
    while(p>0){
        c=o%p;
        o=p;
        p=c;
    }
    q=o;
}
int main()
{
    string x;
    stringstream X;
    while(getline(cin,x)){
        X.clear();
        X.str(x);
        int n=0;
        long long m=1;
        while(X>>n){
            if(n==0){
                return 0;
            }
            GCD(m,n);
            if(q==1){
                m*=n;
            }
            else{
                m=m*n/q;
            }
        }
        cout<<
    }
    return 0;
}

可是還是會超過1S耶??

最快的好像超過兩百微秒??

這題的時間可不可以再長一點ˊˋ?

這題主要是在考快速輸出入的技巧.

稍微看了一下,演算法應該是能AC的. 


我ReJudge後還是WA.


题目中写道:

因為這個數可能很大 所以只要輸出%100000000的結果即可

答案并不一定在int范围内,同样不一定在long long范围内,所以你这样是会溢出的

 
ZeroJudge Forum