## 10680 - LCM

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10680 - LCM

Do I have to make a table by precalculating? I only consider the last digit of every primes less than 1000000 and the times of 2 and 5. I use the cycle of last digit to reduce the work. But I do calculating every time encountering a new number and get TLE. How do I boost my program?

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
try to make a table. think in this way ---
if you know last digit of lcm(1...N) then you can aslo calculate last digit of lcm(1.....(N+1)).
Rakeb

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### and how? can you plz explain a bit more

thanks
abi

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
Thanks for rakeb's hint. I solved it in less than 0.4sec.

To abishek:
Let's make a table, then you might find out that if N is not a power of a prime, table[N] would equal to table[N-1], or you have to find out the answer. You can do some precalculating to reduce the time to do this. And be carefully to the power of 2 and 5, they could make trailing 0's and it would not affect the last non-zero digit.

dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am
anyone give me ouput for those input ?

11
12
16
17
19
20
21
23
80
81
82
96
97
98
99
100
123
111
2342
456
12323
76845
23411
1123
999997
999998
999999
1000000

thanks
Nothing is impossible

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
hello dll, my AC program gives the answer as below:

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

Hope it helps sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Spoiler

Process of finding the LCM of two numbers :

Prime Factorize the two numbers and let
A = 2^a1 * 3^a2 * 5^a3 * .....
B = 2^b1 * 3^b2 * 5^b3 * .....

Then the LCM of the two numbers =
2^max(a1, b1) * 3^max(a2,b2) * 5^max(a3, b3) * ......

So if you know the LCM ( for that matter the last digit ) of 1 to N,
then the last digit of 1 to (N+1) is found by prime factorzing (N+1) and seeing whether any power of prime ( of N + 1) exceeds the previous highest power of the same prime.
The trick is if (N+1) is a power of prime then only will it make any effect.

Eg: if N+1 == 8 ( which is a power of prime - 2^3) then you know that there is no number less than 8 that has a prime fact. of 2^3 or more.
and you also know that 2^2 (3 - 1 = 2) is in the list of 1 to 7..
so multiplying the current lcm ( 1 to 7) with 2 will give you the lcm of
1 -- 8. and so on..

btw you have to mod the lcm every time with 1000000 to ensure no overflow occurs... this method took .334 s to get AC.

sunmoon
New poster
Posts: 4
Joined: Tue Jun 29, 2004 12:50 pm
Contact:

### Hey thanks for that!!

Thanks for the sample output!!! It helped me debug my program!!!
All

ravi,IITM.

Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm
j use this algoritm but j get wa
pleas give me some simple input output
program pased all input who was on forum

#include <stdio.h>

unsigned int pierwsze;
unsigned int fstost;

unsigned int liczp=2;
unsigned int oset;

unsigned int iled;
unsigned int ilep;

unsigned int inline mnoz(unsigned int a,unsigned int b)
{
//printf("monoze %d * %d \n",a,b);

//if(a==0)while(1)printf("lol");
a*=b;

//printf("!!!%d!!!\n",a);

//printf("!%d!\n",a);

return a%10;
}

void inline calc(unsigned int nbr)
{
unsigned int dk,i,j,tmp;

//if(wyny[nbr]!=0){printf("%d\n",wyny[nbr]); return;}
//if(nbr>100000){printf("%d\n",5); return;}

for(i=0;i!=liczp;i++)
{
tmp=pierwsze;
dk=0;
while(1)
{
if(tmp>nbr)break;
// if(tmp<0)while(1)printf("FATAL ERROR");
dk++;
tmp*=pierwsze;
}

if(dk==0)break;

// printf("%d ^ %d*\n",pierwsze,dk);
// dk--;

//while(dk--)oset=mnoz(oset,pierwsze);

if(fstost==2){iled=dk;}
if(fstost==5){ilep=dk;}
if( fstost!=2 && fstost!=5)
{

while(dk--)oset=mnoz(oset,pierwsze);

// tmp=fstost;
//
// while(1)
// {
// if(dk%2==0){dk/=2; tmp*=tmp; oset=mnoz(oset,tmp); if(dk==1)break; }
// if(dk%2==1){dk-=1; oset=mnoz(oset,tmp); if(dk==0)break;}
// }
}

}

dk=iled-ilep;
//printf("!%d!\n",dk);
while(dk--){oset=mnoz(oset,2);}

//printf("LOL");
//wyny[nbr]=oset;
printf("%d\n",oset);
}

main()
{
unsigned int i,j,nbr,tmp;

pierwsze=2;
pierwsze=3;

for(i=6;i<=1000000;i+=6)
{
for(j=0;;j++){ if((i-1)%pierwsze[j]==0)break; if((pierwsze[j]*pierwsze[j])>(i-1)){pierwsze[liczp]=i-1; liczp++; break;}}
for(j=0;;j++){ if((i+1)%pierwsze[j]==0)break; if((pierwsze[j]*pierwsze[j])>(i+1)){pierwsze[liczp]=i+1; liczp++; break;}}
}

for(i=0;i!=liczp;i++)fstost[i]=pierwsze[i]%10;

//for(i=990000;i!=1000000;i++){printf("!%d! \n",i); oset=1; calc(i);}

while(1)
{
scanf("%d",&nbr);
oset=1;
iled=0;
ilep=0;
if(nbr==0)break;
calc(nbr);

}

}

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

### 10680

Pls give the correct answer for the following inputs .
Input
999983
999979
999961
999959
999953
999931
999917
999907
999883
999863
999853
999809
999773
999769
999763
999749
999727
999721
999683
999671
999667
999653
999631
999623
999613
999611
999599
999563
999553
999541
999529
999521
999499
999491
999451
999437
999433
999431
999389
999377
999371
999359
999331
999329
999307
999287
999269
999239
999233
999221
999217
999199
999181
999169
999149
999133
999101
999091
999083
999067
999049
999043
999029
999023
999007
998989
998983
998969
998957
998951
998947
998941
998927
998917
998909
998897
998861
998857
998843
998839
998831
998819
998813
998779
998759
998749
998743
998737
998717
998689
998687
998681
998653
998651
998633
998629
998623
998617
998561
998551
0
Thanks ..
L I M O N

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
my code passed on all output given by htl but i'm getting WA with 0.121sec
so, more I/O will be appriciated.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Here is my output:
8
6
4
4
6
2
2
6
8
6
2
4
6
2
8
6
4
2
2
4
4
2
4
4
8
6
6
4
8
6
6
4
4
6
6
6
8
6
6
4
2
2
8
8
2
6
8
2
8
6
6
8
2
2
8
2
4
4
4
8
4
6
2
8
6
8
2
4
6
8
8
4
4
2
6
4
2
2
6
2
8
8
2
4
6
4
6
2
6
8
2
6
6
2
2
4
6
2
6
6
Hope it helps
JongMan @ Yonsei

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm
my prog pass all tests but get wa L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am