Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=20&page=show_problem&problem=1833
A pair of numbers has a unique LCM but a single number can be the LCM of more than one possible pairs. For example 12 is the LCM of (1, 12), (2, 12), (3,4) etc. For a given positive integer N, the number of different integer pairs with LCM is equal to N can be called the LCM cardinality of that number N. In this problem your job is to find out the LCM cardinality of a number. Input The input file contains at most 101 lines of inputs. Each line contains an integer N (0 < N ≤ 2 ∗ 109 ). Input is terminated by a line containing a single zero. This line should not be processed. Output For each line of input except the last one produce one line of output. This line contains two integers N and C. Here N is the input number and C is its cardinality. These two numbers are separated by a single space.
Sample Input 2 12 24 101101291 0
Sample Output 2 2 12 8 24 11 101101291 5
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
return a==0 ? b : gcd(b%a, a);
}
int lcm(int a, int b){
return a*(b/gcd(a, b));
}
int main()
{
int val;
while(scanf("%d",&val), val!=0){
vector<int> divisor;
// generate all divisor
for(int i=1;i i+It =sqrt(val);i++)
if(val%i == 0){
divisor.push_back(i);
if(val/i != i) divisor.push_back(val/i);
}
// iterate through all pairs of divisor
int res = 0;
for(int i=0;i i+It divisor.size();i++)
for(int j=i;j i+It divisor.size();j++)
if(lcm(divisor[i],divisor[j]) == val)
res++;
printf("%d %d\n",val,res);
}
}
Input
12
24
101101291
0
Output
24 11
101101291 5
Demonstration
UVA Online Judge solution - 10892-LCM Cardinality - UVA Online Judge solution in C,C++,java