Lightoj 1289 - LCM from 1 to n solution in English

 

Lightoj 1289 - LCM from 1 to n solution in English

Problem Link: Lightoj 1289 

Click here to see the discussion in Bangla 

The problem is: we are given a number n. We need to calculate the LCM of all numbers from 1 to n.

At first glance, if we look at the constraints:

• n can be as large as 10^8

• The number of test cases can be as large as 10^4

So if we try to directly compute the LCM by looping through numbers one by one, we will definitely get a TLE (Time Limit Exceeded).

Step 1: Recall how to calculate LCM and GCD

For two numbers a and b, we know:

• Every number can be expressed as a product of prime powers:

  a = p1^x1 * p2^x2 * ...
  b = p1^y1 * p2^y2 * ...
  

• Then:

  gcd(a, b) = p1^min(x1,y1) * p2^min(x2,y2) * ...
  lcm(a, b) = p1^max(x1,y1) * p2^max(x2,y2) * ...
  

Example:

• 20 = 2^2 * 5

• 14 = 2 * 7

gcd(20,14) = 2^min(2,1) * 5^min(1,0) * 7^min(0,1) = 2  
lcm(20,14) = 2^max(2,1) * 5^max(1,0) * 7^max(0,1) = 140

The same principle works for multiple numbers.

So:

lcm(a,b,c,d) = p1^max(x1,y1,z1,m1) * p2^max(x2,y2,z2,m2) * ...

Step 2: How this applies to our problem

We need lcm(1,2,...,n).
This means: for each prime ≤ n, we need the maximum power of that prime that is ≤ n.

Let’s try an example with n = 10:

Numbers:

1,2,3,4,5,6,7,8,9,10

Factorizations:

2 = 2^1
3 = 3^1
4 = 2^2
5 = 5^1
6 = 2*3
7 = 7^1
8 = 2^3
9 = 3^2
10 = 2*5

So:

LCM(1..10) = 2^3 * 3^2 * 5^1 * 7^1 = 2520

Notice:

• All primes ≤ 10 appear at least once in the LCM.

• But for primes like 2 and 3, higher powers also appear (2^3, 3^2).

Step 3: How to get maximum powers efficiently

• For a prime p, the maximum exponent k such that p^k ≤ n is exactly:

  k = floor(log_p(n))
  

• For example, for n = 10:

  • For prime 2: largest power ≤ 10 is 2^3 = 8

  • For prime 3: largest power ≤ 10 is 3^2 = 9

  • For prime 5: largest power ≤ 10 is 5^1 = 5

  • For prime 7: largest power ≤ 10 is 7^1 = 7

That’s exactly what we need.

Step 4: Precomputation strategy

• Generate all primes up to 10^8 using Sieve of Eratosthenes.

• Precompute cumulative product of primes to handle queries faster:

  store[i] = store[i-1] * prime[i]
  

This way, for any n, we know:

• Multiply all primes ≤ n once.

• Then, for primes ≤ sqrt(n), also multiply the extra higher powers.

Step 5: Modulo issue

The problem asks us to take the result modulo 2^32.
If we use unsigned int in C++ (32-bit), the modulo will happen automatically.

So the efficient approach:

1. Generate primes up to 10^8.

2. For each test case:

   • Multiply all primes ≤ n.

   • For each prime ≤ sqrt(n), multiply in the maximum exponent of that prime ≤ n.

3. Result is modulo 2^32.

'