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 »

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 »

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 »

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

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

output..

Post by sohel »

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 »

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 »

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 »

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

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 »

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 »

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 »

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 »

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

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 »

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.

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 »

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 »

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

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 »

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