UVa 10680 - LCM

Accepted date: 2015-07-23
Ranking (as of 2015-07-23): 2 out of 1034
Language: C++

/*
  UVa 10680 - LCM

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10680_LCM.cpp
*/

#include <cstdio>
#include <cmath>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

const int n_max = 1000000,
  sqrt_n_max = static_cast<int>(sqrt(static_cast<double>(n_max)));
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
int power_of_primes[n_max + 1];
  // power_of_primes[i] is a positive number p if i is a power of prime number p, 
  // otherwise 0
long long lcms[n_max + 1]; // lcms[i] is the last nonzero digit of LCM of 1 to i

void sieve_of_eratosthenes()
{
  not_primes[0] = not_primes[1] = true;
  for (int i = 2; i <= sqrt_n_max; i++)
    if (!not_primes[i]) {
      for (int j = i * i; j <= n_max; j += i)
        not_primes[j] = true;
    }
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  sieve_of_eratosthenes();
  for (int i = 2; i <= sqrt_n_max; i++)
    if (!not_primes[i]) {
      for (long long j = static_cast<long long>(i) * i; j <= n_max; j *= i)
        power_of_primes[j] = i;
    }
  lcms[1] = 1; lcms[2] = 2;
  long long l = lcms[2];
  for (int i = 3; i <= n_max; i++) {
    if (!not_primes[i] || power_of_primes[i]) {
      if (!not_primes[i])
        l *= i;
      else
        l *= power_of_primes[i];
      while (!(l % 10))
        l /= 10;
      l %= n_max;
#ifdef DEBUG
      printf("%d: %lld\n", i, l);
#endif
    }
    lcms[i] = l % 10;
  }
#ifdef DEBUG
  printf("%lld\n", lcms[n_max]);
#endif
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    printf("%lld\n", lcms[n]);
  }
  return 0;
}