10680 - LCM

[Martin Macko]

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]

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]

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]

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:

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

.........if(prev>DIGIT)
.....................prev = truncate_digits(prev);.

[mostafiz93]

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]

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

[brianfry713]

http://en.wikipedia.org/wiki/Greatest_common_divisor

[richatibrewal]

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]

You should pre-compute the results for all possible input.