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

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

10680 - LCM

Post by htl » Tue Jun 29, 2004 2:51 pm

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?

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Tue Jun 29, 2004 5:40 pm

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

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

and how? can you plz explain a bit more

Post by abishek » Tue Jun 29, 2004 7:07 pm

thanks
abi

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

Post by htl » Wed Jun 30, 2004 4:41 am

Thanks for rakeb's hint. I solved it in less than 0.4sec.

To abishek:
Let's make a table[1000000], 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

Post by dll » Wed Jun 30, 2004 9:16 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

Post by htl » Wed Jun 30, 2004 9:27 am

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

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

Spoiler

Post by sohel » Wed Jun 30, 2004 12:45 pm

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

Post by sunmoon » Thu Jul 01, 2004 8:26 pm

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

ravi,IITM.

User avatar
Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm

Post by Pavl0 » Tue Jul 06, 2004 8:28 am

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[100000];
unsigned int fstost[100000];


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[0]=2;
pierwsze[1]=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
Location: Dhaka, Bangladesh
Contact:

10680

Post by L I M O N » Wed Jul 07, 2004 12:46 pm

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
Location: BANGLADESH

Post by prince56k » Wed Jul 07, 2004 3:46 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:

Post by Whinii F. » Thu Jul 08, 2004 7:06 am

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

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

Post by sohel » Thu Jul 08, 2004 1:59 pm


User avatar
Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm

Post by Pavl0 » Fri Jul 09, 2004 10:21 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
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Sat Jul 10, 2004 9:54 am

Thanks Whinii F !!
I already got accepted .

L I M O N

Post Reply

Return to “Volume 106 (10600-10699)”