10680 - LCM

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10680 - TLE! Why?

Post by Martin Macko » Sat Aug 05, 2006 3:27 am

And btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewto ... ight=10680, http://online-judge.uva.es/board/viewto ... ight=10680 and http://online-judge.uva.es/board/viewto ... ight=10680)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10680

Post by Martin Macko » Sat Aug 05, 2006 3:27 am

And btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewto ... ight=10680, http://online-judge.uva.es/board/viewto ... ight=10680 and http://online-judge.uva.es/board/viewto ... ight=10680)

jbh
New poster
Posts: 4
Joined: Fri Aug 04, 2006 7:33 pm

Post by jbh » Sat Aug 05, 2006 1:28 pm

ok martin, i'll do that in future.
but help me on this code. i know it gives wa for some inputs.
but i can't find the problem. :(

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 06, 2006 12:06 am

jbh wrote:ok martin, i'll do that in future.
but help me on this code. i know it gives wa for some inputs.
but i can't find the problem. :(
Firstly, you get an overflow here:
seive() wrote:...for(int i=2;i*i<=size_;i++){
......if(prime[i]){
.........for(int j=i*i;j<=size_;j+=i){.........<-- here i*i is bigger than 2^31 for large i
............prime[j]=false;
.........}
......}
...}
Secondly, I don't believe you can do the following without loss of inportant information:
lcm() wrote:.........if(prev>DIGIT)
.....................prev = truncate_digits(prev);.

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 10680 - LCM

Post by mostafiz93 » Wed Apr 25, 2012 11:01 pm

i'm getting wrong answer in this problem.
i've generated output for all 1 to 1000000 cases with both my code and an accepted code, but find no difference after checking!
can anybody help me?
my code is here:

Code: Select all

removed after ac

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10680 - LCM

Post by raj » Thu Feb 21, 2013 4:25 pm

CAN ANYONE TELL ME THE FORMULA OF
GCD(X,Y,Z)???????? :(
LCM(X,Y,Z)??????? :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10680 - LCM

Post by brianfry713 » Thu Feb 21, 2013 11:06 pm

Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Why TLE??

Post by richatibrewal » Thu Dec 18, 2014 2:34 pm

I am getting TLE for the following code:

Code: Select all

#include<cstdio>
#include<cmath>
#include<vector>
#define max 1000000
using namespace std;
bool mark[max+10];
vector<int> prime;
void sieve()
{
    int i,j,p;
    for(i=2;i<=max+10;i++)
        mark[i]=true;
    p=(float)pow(max+10,0.5);
    for(i=2;i<=p;i++)
    {
        if(mark[i])
            for(j=i*i;j<=max+10;j=j+i)
                mark[j]=false;
    }
    for(i=2;i<=max+10;i++)
        if(mark[i])
            prime.push_back(i);
    i=prime[1];
    prime[1]=prime[2];
    prime[2]=i;
}
int main()
{
    sieve();
    int p2,p5,i,j,res,n,k;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
        break;
        p2=p5=0;
        for(i=2;i<=n;i=i*2)
            p2++;
        for(i=5;i<=n;i=i*5)
            p5++;

        res=1;
        for(i=1;i<=(p2-p5);i++)
            res=(res*2)%10;
        for(i=2;prime[i]<=n;i++)
        {
            j=(log10(n))/log10(prime[i]);
            k=(float)pow(prime[i],j);
            res=(res*k)%10;
        }
        printf("%d\n",res);
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10680 - LCM

Post by brianfry713 » Sat Dec 20, 2014 3:24 am

You should pre-compute the results for all possible input.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 106 (10600-10699)”