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

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

Post by dpitts » Thu Oct 21, 2004 10:27 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

Post by dpitts » Thu Oct 21, 2004 10:41 pm

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

Fixed that and got AC

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

10680 can u help

Post by inproblem » Sun Oct 31, 2004 12:04 am

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

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

output..

Post by sohel » Sun Oct 31, 2004 9:54 am

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

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Post by frankhuhu » Tue Nov 09, 2004 3:40 am

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.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Mar 30, 2005 10:39 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.

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

10680 - TLE! Why?

Post by medv » Tue Oct 04, 2005 9:33 am

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);
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10680 - TLE! Why?

Post by Martin Macko » Sat Dec 10, 2005 11:56 pm

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.

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

10680

Post by scidong » Fri Feb 03, 2006 2:02 pm

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.
一八???

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

Post by mf » Fri Feb 03, 2006 3:07 pm

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.

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

10680 WA

Post by a123123123888 » Sun Jul 02, 2006 5:08 am

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

Code: Select all

#define MAX 78599
int 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]);
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10680 WA

Post by Martin Macko » Sun Jul 23, 2006 11:17 pm

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10680 WA

Post by Martin Macko » Sun Jul 23, 2006 11:20 pm

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

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

10680

Post by jbh » Fri Aug 04, 2006 8:38 pm

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 1000000

bool 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;
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10680

Post by Martin Macko » Sat Aug 05, 2006 3:22 am

jbh wrote:my code gives wrong output for some input like 78125. but why? plz help me.
Your solution isn't working for:

Code: Select all

397979
0
My AC's output:

Code: Select all

6

Post Reply

Return to “Volume 106 (10600-10699)”