Each pair of integers has a unique LCM:
lcm(a, b) = a * b / gcd(a, b)
Note that gcd(a, b) is unque too.
The LCM cardinality for an integer (n
) is the number of distinct pairs of integers (a
& b
) that satisfy:
n = lcm(a, b)
A few Examples:
6 8 9 12 ===== ===== ===== ===== 1, 6 1, 8 1, 9 1, 12 2, 6 2, 8 3, 9 2, 12 3, 6 4, 8 9, 9 3, 12 6, 6 8, 8 ----- 4, 12 ----- ----- 3, 3 6, 12 2, 3 2, 4 12,12 ----- 2, 6 3, 4 ===== ===== ===== ===== 5 5 4 8
After observing the pattern, what we’re actually doing is: we are counting the number of factors of the integer n
, HOWEVER, factors less than or equal to the root of n
are counted twice (except the factor 1
).
For example the cardinality of 16:
factor 1 2 4 8 16 factor <= 4 true true true false false lcm cardinality = 1 + 2 + 2 + 1 + 1 = 7
We can implement this either with pre-calculation or factorization.
#include <iostream> #include <climits> #include <cstdlib> using namespace std; const int N = 5000; int lcmCardinality[N]; void calculate() { // 1 lcmCardinality[1] = 1; for (int i = 2; i < N; ++i) lcmCardinality[i] = 0; // other for (int i = 2; i < N; ++i) { // less than root for (int j = i; j <= i * i && j <= N; j += i) lcmCardinality[j] += 2; // more if (i + 1 < INT_MAX / i) for (int j = i * (i + 1); j <= N; j += i) lcmCardinality[j]++; } } int main() { calculate(); int n; while (cin >> n) cout << lcmCardinality[n] << endl; return 0; }