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

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

Re: 10680 - TLE! Why?

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)

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

Re: 10680

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
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.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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

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

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

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??

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

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