10680 - LCM

[dpitts]

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

Fixed that and got AC

[dpitts]

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

Fixed that and got AC

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

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]

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]

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]

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]

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]

Plz help me...
How can i calculate LCM?
p.s. Please don`t delete this question. It is 10680!

[mf]

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]

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]

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]

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

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

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