10680 - LCM

[htl]

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]

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

[abishek]

thanks
abi

[htl]

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]

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

[htl]

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]

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]

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

[Pavl0]

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[i];
dk=0;
while(1)
{
if(tmp>nbr)break;
// if(tmp<0)while(1)printf("FATAL ERROR");
dk++;
tmp*=pierwsze[i];
}

if(dk==0)break;

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

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

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

while(dk--)oset=mnoz(oset,pierwsze[i]);

// tmp=fstost[i];
//
// 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]

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]

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

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

[sohel]

here is some more:

http://online-judge.uva.es/board/viewto ... highlight=

[Pavl0]

my prog pass all tests but get wa

[L I M O N]

Thanks Whinii F !!
I already got accepted .

L I M O N