10680 - LCM
Moderator: Board moderators
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?
and how? can you plz explain a bit more
thanks
abi
abi
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.
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.
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.
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.
Hey thanks for that!!
Thanks for the sample output!!! It helped me debug my program!!!
All
ravi,IITM.
ravi,IITM.
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);
}
}
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);
}
}
-
- Learning poster
- Posts: 58
- Joined: Wed Dec 31, 2003 8:43 am
- Location: Dhaka, Bangladesh
- 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
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