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

530 – Binomial Showdown

This problem is identical to 369 – Combinations.

369 – Combinations

A combinations problem. Given N and R, find NCR.
There’s a variety of ways; The first two solutions are straight-forward computation of . The last two have some tricks:

A naive Java solution that uses big arithmetic:

import java.math.*;
import java.util.*;

public class Main {

	private static BigInteger C(BigInteger n, BigInteger r) {
		r = (r.compareTo(n.subtract(r)) > 0) ? n.subtract(r) : r;
		BigInteger num = BigInteger.ONE, den = BigInteger.ONE;
		while (!r.equals(BigInteger.ZERO)) {
			num = num.multiply(n); den = den.multiply(r);
			r = r.subtract(BigInteger.ONE); n = n.subtract(BigInteger.ONE);
		}
		return num.divide(den);
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while (s.hasNext()) {
			BigInteger n = s.nextBigInteger(), r = s.nextBigInteger();
			if (n.equals(BigInteger.ZERO) && r.equals(BigInteger.ZERO))
				break;
			System.out.printf("%s things taken %s at a time is %s exactly.\n", n, r, C(n, r));
		}
	}
}

A similar C++ solution:

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

unsigned long long C(int n, int r) {
	r = min(n - r, r);
	long long out = 1;
	for (int i = 1; i <= r; ++i) {
		out *= n - r + i;
		out /= i;
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

A slower, but totally accepted, solution reduces the computations as you were doing it by hand; We have two arrays, one for the numerator and another for the denominator. We do a 2D loop to reduce the numerator with respect to the denominator and hence the answer. C++ implementation:

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

#define REDUCE(a, b) { int g = gcd(a, b); a /= g; b /= g; }

int num[100], den[100];
int numI, denI;

long long gcd(long long a, long long b) {
	long long t;
	while (a) { t = a; a = b % a; b = t; }
	return b;
}

long long C(int n, int r) {
	// fill arrays
	r = min(n - r, r);
	numI = denI = 0;
	while (r) { num[numI++] = n--; den[denI++] = r--; }
	// reduce & compute
	long long out = 1;
	for (int i = 0; i < numI; ++i) {
		for (int j = 0; j < denI; ++j)
			REDUCE(num[i], den[j]);
		out *= num[i];
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

The last solution has the same complexity as the first two. It uses Pascal’s Triangle for computing combinations. C++ implementation:

#include <cstdio>
using namespace std;

#define N 128

long long pascalTri[N * (N + 1) / 2];

void fillPascal() {
	for (int l = 0, lStart = 0; l < N; ++l, lStart += l) {
		pascalTri[lStart] = pascalTri[lStart + l] = 1;
		for (int i = 1; i < l; ++i)
			pascalTri[lStart + i] = pascalTri[lStart + i - l] + pascalTri[lStart + i - l - 1];
	}
}

int main() {
	fillPascal();
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, pascalTri[n * (n + 1) / 2 + r]);
	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;
}

12149 – Feynman

A combinatorics problem.
You’re required to count the number of squares in an NxN square grid.
After observing some base cases you might recognize the formula if you’re familiar with it. However, let’s try a more systematic and intuitive way. In an NxN area, we’ll look into squares that inhibit this area with respect to their dimensions:

• 1x1 squares: each one of these can choose an x-position from 1 to N. Also, a y-position from 1 to N. Thus, it can choose out of NxN position.
• 2x2 squares: which are bigger by one. Thus, they can choose between N-1 x-positions and N-1 y-positions. That’s (N-1)x(N-1)
• 3x3 squares: using similar reasoning are (N-2)x(N-2).
• NxN squares: 1x1 (only one possible position).
• And so on…

Hence the formula we get is:

Which is the square pyramidal number. OEIS.
Coded in C++ with rank 574:

#include <cstdio>
using namespace std;

long long n;

int main() {
	while (scanf("%lld", &n) && n)
		printf("%lld\n", n (n + 1) (2 n + 1) / 6);
	return 0;
}