10680 - LCM

Moderator: Board moderators

My first mistake was not including 1000000 in my pre calculations.

Fixed that and got AC
dpitts
New poster

Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

My first mistake was not including 1000000 in my pre calculations.

Fixed that and got AC
dpitts
New poster

Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

10680 can u help

anyone wht got ac in this problem can u give me the output for these inputs

128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
25
125
625
3125
15625
78125
390625
inproblem
New poster

Posts: 4
Joined: Fri Oct 29, 2004 9:52 pm

output..

My AC program produces the following output..

2
6
2
2
2
4
4
6
6
6
4
2
6
4
8
8
4
8
6
4

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

I have passed all the test cases above. But still WA.Who can tell me why?
Is there any possible that if n=1 the output should be 1.
frankhuhu
New poster

Posts: 30
Joined: Tue Jul 20, 2004 5:22 am

1. generate all primes upto 10^6

2. generate all powers of each prime
Code: Select all
`   for ( i = 0; i <= MAX; ++i ) D[i] = 1;    for ( i = 1L; (1L<<i) <= MAX; ++i )    {        D[(1L<<i)] = 2L;    }    for ( i = 3L; i < MAXSQRT; i += 2L )    {        if ( isprime(i) )        {            for ( j = i; j <= MAX; j *= i )            {                D[j] = i;            }        }    }    for ( ; i <= MAX; i += 2L )    {        if ( isprime(i) )        {            D[i] = i;        }    }`

3. calculate the lcm using the following
Code: Select all
`         lcm (n) = lcm(n-1) * D(n),where           D(n) = n ,iff n is prime          D(n) = p, where n = p^k, k is any +ve integer and p is a prime             D(n) = 1, otherwise`

Code: Select all
`    D[1] = 1L;    for ( i = 2L; i <= MAX; ++i )    {                if ( D[i] == 5L )        {            D[i] = (D[i-1]>>1L);        }        else        {            D[i] = (D[i]%1000000L)*(D[i-1]%1000000L);        }        while ( (D[i]%10L) == 0 )            D[i] /= 10L;        D[i] %= 1000000L;    }`

Any thoughts regarding the algorithm I am using?

Regards,
Suman.
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

10680 - TLE! Why?

I don't know why TLE
How can I speed up a program?

#include <stdio.h>
#include <math.h>
#include <memory.h>

const int MAX=1000001;
const int SqrtMAX = (int)sqrt(MAX);
int m[MAX];
int i,n;

void gen_mas_m(void)
{
int i,j;
memset(m,127,sizeof(m)); m[0] = m[1] = 1;
for(i=2;i<=SqrtMAX;i++)
if (m[i] == 0x7F7F7F7F)
{
for(j=i*i;j<=MAX;j+=i) m[j] = 0;
for(j=i;j<=MAX;j*=i) m[j] = i % 10;
}
for(i=SqrtMAX;i<=MAX;i++)
if (m[i] == 0x7F7F7F7F) m[i] = i % 10;
}

void main(void)
{
gen_mas_m();
for(i=2;i<=MAX;i++)
{
if (!m[i]) m[i] = 1;
m[i] = m[i]*m[i-1] % 100;
if (m[i] % 10 == 0) m[i] = m[i] / 10;
}
while (scanf("%d",&n), n>0)
printf("%d\n",m[n] % 10);
}
medv
Learning poster

Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Re: 10680 - TLE! Why?

medv wrote:int m[MAX];
int i,n;
...
..for(i=2;i<=MAX;i++)
..{
....if (!m[i]) m[i] = 1;..
....m[i] = m[i]*m[i-1] % 100;
....if (m[i] % 10 == 0) m[i] = m[i] / 10;
..}

at the end of the loop if i==MAX you change the value of m[MAX]. But m[MAX] is out of the array bounds (0..MAX-1), thus you may corrupt the information stored in other variable.

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

10680

Plz help me...
How can i calculate LCM?
p.s. Please don`t delete this question. It is 10680!
All living things are amazing thing.

scidong
New poster

Posts: 45
Joined: Sat Jan 21, 2006 12:55 pm
Location: the four-dimensional world

scidong wrote:How can i calculate LCM?

LCM of two numbers is: lcm(a,b) = a*b/gcd(a,b).
LCM of n numbers can be computed as: lcm(a1,a2,...,a_n) = lcm(a1, lcm(a2, a3, ..., a_n)).
There is also another way to compute LCM: exponent of a prime p in factorization of lcm(a1, a2, ..., a_n) is the maximum exponent of that prime in factorizations of a1, a2, ..., a_n.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

10680 WA

Can anyone say where is wrong?
I try to solve it but fault
Code: Select all
`#define MAX 78599int a[1000009];int prime[MAX]={2,3,5},pows[168];void calprime(){   int i,j,k,flag;   for(i=3,j=7;i<MAX;j++,flag=1)   {      for(k=0;prime[k]*prime[k]<=j;k++)         if(j%prime[k]==0)         {            flag=0;            break;         }      if(flag)         prime[i++]=j;   }}void precal(){   int i,j,k=168,min,who,temp,last,five=0,two=0;   a[1]=1;   for(i=0;i<168;i++)      pows[i]=prime[i];   for(min=12345678,j=2;;min=12345678)   {      for(i=0;i<168;i++)         if(min>pows[i])         {            min=pows[i];            who=i;         }      if(prime[k]<min)      {         who=k;         min=prime[k];         k++;      }      for(;j<=min&&j<=1000000;j++)         a[j]=a[j-1];      if(j>1000000)         break;      if(who==2)      {         five++;         last=(1<<(two-five))%10;         for(i=1;i<168;i++)         {            if(i==2)               continue;            last*=(pows[i]/prime[i])%10;            last%=10;         }         for(i=168;i<k;i++)         {            last*=prime[i]%10;            last%=10;         }         a[min]=last;         pows[who]*=prime[who];      }      else      {         if(who==0)            two++;         a[min]*=prime[who]%10;         a[min]%=10;         if(who<168)            pows[who]*=prime[who];      }   }}int main(){   int n,i;   calprime();   precal();   while(scanf("%d",&n),n)      printf("%d\n",a[n]);}`
a123123123888
New poster

Posts: 7
Joined: Fri Mar 31, 2006 1:22 pm

Re: 10680 WA

a123123123888 wrote:Can anyone say where is wrong?
I try to solve it but fault

It's really interesting that your solution gets WA, while my gets AC, as both of them give the same answers to all numbers between 1 and 1000000.

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10680 WA

and btw, if there is a thread on a particular problem, please, use that thread and do not create a new one.

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

10680

my code gives wrong output for some input like 78125. but why? plz help me.
Code: Select all
`#include<stdio.h>#include<math.h>#include<string>#include<iostream>#include<stdlib.h>#include<ctype.h>using namespace std;#define tt long long#define type int#define size_ 1000001#define DIGIT 1000000bool prime[size_];bool flag[size_];int arr[size_];int P[size_];void seive(){   memset(prime,true,sizeof(prime));   prime[0]=false;   prime[1]=false;   for(int i=2;i*i<=size_;i++){         if(prime[i]){               for(int j=i*i;j<=size_;j+=i){                     prime[j]=false;                  }            }      }}void to_power(){   memset(flag,false,sizeof(flag));   for(int i=0;i<size_;i++){         if(prime[i]){               for(int j=i*i;j<size_ && j>0;j=j*i){                     flag[j]=true;            P[j]=i;         }      }   }}tt extra_zero(tt a){   while(a%10==0){         a/=10;   }   return a;}tt truncate_digits(tt a){   return a%DIGIT ;}int last_digit(tt a){   return a%10;}void lcm(){   arr[0]=0;   arr[1]=1;   tt prev;   prev = 1;   for(int i=2;i<=size_;i++){   //      printf("i= %d  prev_before=  %I64d  ",i,prev);//      printf("is_prime[%d]=%d  is_pow[%d]=%d  ",i,prime[i],i,P[i]);      if(prime[i]){               prev*=i;         if(prev%10==0)            prev = extra_zero(prev);         if(prev>DIGIT)            prev = truncate_digits(prev);         arr[i]=prev;            }      else if(flag[i]){               prev*=P[i];         if(prev%10==0)            prev = extra_zero(prev);         if(prev>DIGIT)            prev = truncate_digits(prev);         arr[i]=prev;            }      else{               arr[i]=arr[i-1];      }//      printf("prev_after   %I64d\n",prev);      }}int main(){   seive();   to_power();   lcm();   int i,j;//   freopen("10680.txt","rt",stdin);      while(scanf("%d",&i)==1){            if(i==0)         return 0;      j = arr[i];      j = last_digit(extra_zero(j));               printf("%d\n",j);      }   return 0;}`
jbh
New poster

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

Re: 10680

jbh wrote:my code gives wrong output for some input like 78125. but why? plz help me.

Code: Select all
`3979790`

My AC's output:
Code: Select all
`6`

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

PreviousNext