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

1213 – Sum of Different Primes

A Dynamic Programming problem.
Simply, you combine primes — which you generated one way or another — that add up to the input. This combination should be executed via Dynamic Programming. Your state consists of:

• n – the number that needs decomposition.
• k – the number of primes n should be divided into.
• i – the lowest prime number that can be used in the next decomposition. This is to avoid repeated primes in the sum.

Your transitions from S(n, k, i) are:

• S(n – prime[i], k – 1, i + 1) – subtract the current prime.
• S(n, k, i + 1) – bypass it.

C++ implementation:

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

#define N 2048
#define P 309
#define K 16

long long nWays[N][K][P], prime[P];

void sieve() {
	int nPrime = 0, isPrime[N];
	memset(isPrime, true, sizeof isPrime);
	isPrime[0] = isPrime[1] = true;
	for (int i = 2; i < N; ++i)
		if (isPrime[i] && (prime[nPrime++] = i))
			for (int j = i * i; j < N; j += i)
				isPrime[j] = false;
}

long long getNWays(int n, int k, int i) {
	if (n == 0 && k == 0)
		return 1;
	if (n < 0 || k < 0 || prime[i] > n || i == P)
		return 0;
	if (nWays[n][k][i] != -1)
		return nWays[n][k][i];
	return nWays[n][k][i] = getNWays(n - prime[i], k - 1, i + 1) + getNWays(n, k, i + 1);
}

int main() {
	// init
	sieve();
	memset(nWays, -1, sizeof nWays);
	// solve
	int n, k;
	while (cin >> n >> k && (n || k))
		cout << getNWays(n, k, 0) << endl;
	return 0;
}

10637 – Coprimes

A math backtracking problem.
You’re required to find T coprime integers that sum up to a given integer S. A basic brute-force solution gets all possible non-descending lists of T integers that sum up to S and then check for coprimality (filter). Better yet, you could early prevent lists that already broke the coprimality rule from continuing to construct (generator).
That was the backtracking part. On to the math. To check for the coprimality of N integers, you have to do N! operations and that’s not good. So, we’ll have a bitmask M for each number N that tells N‘s prime factors. The i^th bit M tells whether N divides the i^th prime. This facilitates a lot of stuff:

• Initialize a cumulative bitmask M to 0.
• Choose a new integer I for the list.
• I is good, if none of I‘s prime factors is already used in the list (factor[I] & M == 0).
• Upon adding I to the list, M accumulates I‘s prime factors (M = M | factor[I]).
• Repeat the above as long as the list is incomplete.
• When the list is full, print.

C++ implementation with a pre-calcuated prime factor bitmask array. Rank 46:

#include <cstdio>
using namespace std;

int factor[] = { "http://pastebin.com/crP26nmh" };

unsigned int S, T;
int coprimes[32];

void print() {
	printf("%d", coprimes[0]);
	for (unsigned int i = 1; i < T; ++i)
		printf(" %d", coprimes[i]);
	printf("\n");
}

void solve(int m, int s, int l, unsigned int t) {
	if (t == T && s == 0)
		print();
	else if (t < T)
		for (int i = l; i <= s; ++i)
			if ((factor[i] & m) == 0) {
				coprimes[t] = i;
				solve(factor[i] | m, s - i, i, t + 1);
			}
}

int main() {
	int nCase;
	scanf("%d", &nCase);
	for (int caseI = 0; caseI < nCase; ++caseI) {
		// input
		scanf("%d %d", &S, &T);
		// output
		printf("Case %d:\n", caseI + 1);
		// solve
		solve(0, S, 1, 0);
	}
	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;
}

10924 – Prime Words

A simple prime number problem. Sum the values of the characters and check for primality. C++ code:

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

#define N 2048
#define VAL(c) (c > 'Z' ? (c - 'a' + 1) : (c - 'A' + 27))

bool notPrime[N];

void sieve() {
	notPrime[0] = true;
	for (int i = 2; i < N; ++i)
		if (!notPrime[i])
			for (int j = i * i; j < N; j += i)
				notPrime[j] = true;
}

char line[32], sol[2][128] = { "It is a prime word.", "It is not a prime word." };
int i, sum;

int main() {
	sieve();
	while (scanf("%s", line) == 1) {
		for (sum = i = 0; line[i]; ++i)
			sum += VAL(line[i]);
		printf("%s\n", sol[notPrime[sum]]);
	}
	return 0;
}