LCM Cardinality

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.

Pre-calculation

#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;
}

160 – Factors and Factorials

A simple math problem.
For , you’re required to find the number of its prime factors. The input space is n < 100 which is rather small. So, a pre-calculation will do. For each integer starting from 0 up to 100, calculate the number of prime factors and there repetition and store them in a 100×25 array (25 is the number of prime numbers under 100).
Now, for any input n, we iterate over all the numbers form 1 to n and accumulate their prime factors repetition in an array of length 25.
Caution!

• Output is tricky.

C++ code, rank 5311:

#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;

#define N 101

int nFactors[101][25] = {
	"http://pastebin.com/RAANwCY0#"
	};

int main() {
	int n;
	int nDiv[25];
	while(scanf("%d", &n) && n) {
		memset(nDiv, 0, sizeof nDiv);
		// add factors
		for (int i = 2; i <= n; ++i)
			for (int j = 0; j < 25; ++j)
			nDiv[j] += nFactors[i][j];
		// print
		printf("%3d! =", n);
		int nBlock = 0;
		for (int i = 0; i < 25; ++i)
			if(nDiv[i]) {
				if(nBlock == 15) {
					nBlock = 0;
					printf("\n      ");
				}
				printf("%3d", nDiv[i]);
				++nBlock;
			}
		printf("\n");
	}
	return 0;
}

993 – Product of digits

A factorization problem.
A straight-forward solution would be dividing the input by the numbers from 9 down to 2 and build the output. If after these divisions the input has value other than 1, then it can’t be solved (there are factors larger than 9).
C++ implementation:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long int64;

int n;
int64 q, d;

int main() {
	int nCase;
	scanf("%d", &nCase);
	while (nCase--) {
		// in
		scanf("%d", &n);
		if (n == 0) {
			printf("10\n");
			continue;
		} else if (n < 10) {
			printf("%d\n", n);
			continue;
		}
		d = (q = 0) + 1;
		// solve
		for (int i = 9; i > 1; --i)
			while (n % i == 0) {
				n /= i;
				q += i * d;
				d *= 10;
			}
		// out
		if (n == 1)
			printf("%lld\n", q);
		else
			printf("-1\n");
	}
	return 0;
}

382 – Perfection

A perfect number is a number which is equal to sum of its divisors.
We first generate the sum of divisors for the first 60000 integers (60000 = max input), then, when given a test case, use the sum in an if-else check that tells the number’s perfection.
The generation step is quite simple:

for (int i = 1; i < N; ++i)
	for (int j = 2 * i; j < N; j += i)
		divisorSum[j] += i;

C++ implementation:

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;

typedef unsigned long long int64;
#define OUT(n, d) (n < d ? "ABUNDANT" : (n == d ? "PERFECT" : "DEFICIENT"))
#define N 65536

int64 divisorSum[N];

void init() {
	for (int i = 1; i < N; ++i)
		for (int j = 2 * i; j < N; j += i)
			divisorSum[j] += i;
}

int main() {
	// init
	memset(divisorSum, 0, sizeof divisorSum);
	init();
	int64 n;
	// in & out
	cout << "PERFECTION OUTPUT" << endl;
	while (cin >> n && n)
		cout << setw(5) << n << "  " << OUT(n, divisorSum[n]) << endl;
	cout << "END OF OUTPUT" << endl;
	return 0;
}

136 – Ugly Numbers

An ad-hoc brute-force problem.
You iterate over all integers, check if they’re ugly and stop when you reach the required number of ugly numbers. Here’s how I made that subrotine:

#include <cstdio>
using namespace std;

#define N 1500
#define F 3
unsigned int f[F] = { 2, 3, 5 };

int main() {
	unsigned long long i;
	int c = 0;
	for (i = 1; c < N; ++i) {
		unsigned long long t = i;
		for (int j = 0; j < F; ++j)
			while (t % f[j] == 0)
				t /= f[j];
		if (t == 1)
			c++;
	}
	printf("%lld\n", i - 1);
	return 0;
}

It’s just a single line of output:

#include <cstdio>
using namespace std;

int main() {
	printf("The 1500'th ugly number is ???.\n");
	return 0;
}

It wouldn’t be proper to provide the final answer. Maybe get ??? through a riddle: “Ate five cops plus eighty five and three times three is nine too”.