USACO BRHS10A Problem 'comdivs' Analysis

by Damon Doucet

This is one of the more complicated problems from this contest, but there are several ways to approach it.

Here's one of Neal's solutions--it's very concise, but heavily relies on the STL, so don't fret if you don't understand it much. You can always learn more about the STL at [1].

#include <set>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream in("comdivs.in");
ofstream out("comdivs.out");

int A, B;

set <int> divisors (int n)
{
    set <int> s;

    for (int i = 1; i * i <= n; i++)
        if (n % i == 0)
        {
            s.insert (i);
            s.insert (n / i);
        }

    return s;
}

int main ()
{
    in >> A >> B;
    set <int> AD = divisors (A), BD = divisors (B);
    int *array = new int [min (AD.size (), BD.size ())];
    out << set_intersection (AD.begin (), AD.end (), BD.begin (),
BD.end(), array) - array << "\n";
    return 0;
}

(Note, the above solution could be coded without the use of the STL. You should try it.;) )

Another of Neal's solutions relies on the following idea: The common factors between two numbers is the same as the number of factors in their GCD (greatest common divisor). Neal recursively calculates the GCD, then simply counts the factors of that number.

Here it is in code:

#include <fstream>
using namespace std;

ifstream in("comdivs.in");
ofstream out("comdivs.out");

int A, B;

int gcd (int a, int b)
{
    return a == 0 ? b : gcd (b % a, a);
}

int divisors (int n)
{
    int num = 0;

    for (int i = 1; i * i <= n; i++)
        if (n % i == 0)
        {
            num += 2;

            if (i * i == n)
                num--;
        }

    return num;
}

int main ()
{
    in >> A >> B;
    out << divisors (gcd (A, B)) << "\n"; 
    return 0;
}