Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1621
All of you know about LCM (Least Common Multiple). For example LCM of 4 and 6 is 12. LCM can also be defined for more than 2 integers. LCM of 2, 3, 5 is 30. In the same way we can define LCM of first N integers. The LCM of first 6 numbers is 60. As you will see LCM will increase rapidly with N. So we are not interested in the exact value of the LCM but we want to know the last nonzero digit of that. And you have to find that effeciently. Input Each line contains one nonzero positive integer which is not greater than 1000000. Last line will contain zero indicating the end of input. This line should not be processed. You will need to process maximum 1000 lines of input. Output For each line of input, print in a line the last nonzero digit of LCM of first 1 to N integers.
Sample Input 3 5 10 0
Sample Output 6 6 2
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
#define N 1000001
int main() {
bitset < N> isPrime;
isPrime.set();
isPrime[0] = isPrime[1] = false;
vector<int> basePrime(N,1);
// sieve
for(long long i=2;i i+It N;i++){
if(isPrime[i]){
for(long long j=i*i;j i+It N;j+=i)
isPrime[j] = false;
for(long long j=i;j i+It N;j*=i)
basePrime[j] = i; // j = i^x, so has base prime of i
}
}
// dp to compute lcm of 1...n
vector i+It long long> dp(N);
dp[1] = 1;
for(int i=2;i i+It N;i++)
dp[i] = (dp[i-1]*basePrime[i])%1000000000;
int v;
while (scanf("%d",&v), v) {
long long res = dp[v];
// filter zeros
while (res % 10 == 0)res /= 10;
// first non-zero
res = res%10;
printf("%lld\n",res);
}
}
Input
5
10
0
Output
6
2
Demonstration
UVA Online Judge solution - 10680-LCM - UVA Online Judge solution in C,C++,java