Divisibility

If you've never encountered any number theory before, AoPS is a good place to start.

Resources

Prime Factorization

A number $a$ is called a divisor or a factor of a number $b$ if $b$ is divisible by $a$, which means that there exists some integer $k$ such that $b=ka$. Conventionally, $1$ and $n$ are considered divisors of $n$. A number $n>1$ is prime if its only divisors are $1$ and $n$. Numbers greater than (1) that are not prime are composite.

Every number has a unique prime factorization: a way of decomposing it into a product of primes, as follows:

where the $p_i$ are distinct primes and the $a_i$ are positive integers.

Now, we will discuss how to find the prime factorization of an integer.

1vector<int> factor(int n) {
2    vector<int> ret;
3    for (int i = 2; i * i <= n; i++) {
4        while (n % i == 0) {
5            ret.push_back(i);
6            n /= i;
7        }
8    }
9    if (n > 1) ret.push_back(n);
10    return ret;

1ArrayList<Integer> factor(int n) {
2    ArrayList<Integer> factors = new ArrayList<>();
3    for (int i = 2; i * i <= n; i++) {
4        while (n % i == 0) {
5            factors.add(i);
6            n /= i;
7        }
8    }
9    if (n > 1) factors.add(n);
10    return factors;

1def factor(n):
2    ret = []
3    i = 2
4    while i * i <= n:
5        while n % i == 0:
6            ret.append(i)
7            n //= i
8        i += 1
9    if n > 1:
10        ret.append(n)

This algorithm runs in $\mathcal{O}(\sqrt{n})$ time, because the for loop checks divisibility for at most $\sqrt{n}$ values. Even though there is a while loop inside the for loop, dividing $n$ by $i$ quickly reduces the value of $n$, which means that the outer for loop runs less iterations, which actually speeds up the code.

Let's look at an example of how this algorithm works, for $n=252$.

At this point, the for loop terminates, because $i$ is already 3 which is greater than $\lfloor \sqrt{7}\rfloor$. In the last step, we add $7$ to the list of factors $v$, because it otherwise won't be added, for a final prime factorization of $\{2,2,3,3,7\}$.

Solution - Counting Divisors

The most straightforward solution is just to do what the problem asks us to do - for each $x$, find the number of divisors of $x$ in $\mathcal{O}(\sqrt{x})$ time.

1#include <bits/stdc++.h>
2using namespace std;
3 
4int main() {
5    ios_base::sync_with_stdio(0);
6    cin.tie(0);
7    int n;
8    cin >> n;
9    while (n--) {
10        int x, ans = 0;

1import java.io.*;
2import java.util.*;
3
4public class Main {
5    static int solve(int n) {
6        int divisors = 0;
7        for (int i = 1; i * i <= n; i++) {
8            if (n % i == 0) {
9                if (i * i == n) divisors++;
10                else divisors += 2;

This solution runs in $\mathcal{O}(n\sqrt{x})$ time, which is just fast enough to get AC. However, we can actually speed this up to get an $\mathcal{O}((x+n)\log x)$ solution!

First, let's discuss an important property of the prime factorization of a number. Consider:

Then the number of divisors of $x$ is simply $(a_1+1)\cdot (a_2+1)\cdots (a_k+1)$.

Why is this true? The exponent of $p_i$ in any divisor of $x$ must be in the range $[0,a_i]$ and each different exponent results in a different set of divisors, so each $p_i$ contributes $a_i+1$ to the product.

$x$ can have $\mathcal{O}(\log x)$ distinct prime factors, so if we can find the prime factorization of $x$ efficiently, we can answer queries in $\mathcal{O}(\log x)$ time instead of the previous $\mathcal{O}(\sqrt{x})$ time.

Here's how we find the prime factorization of $x$ in $\mathcal{O}(\log x)$ time with $\mathcal{O}(x\log x)$ preprocessing:

• For each $k\le 10^6$, find any prime number that divides $k$.
  • We can use the Sieve of Eratosthenes to find this efficiently.
• For each $x$, we can then find the prime factorization by repeatedly dividing $x$ by a prime number that divides $x$ until $x=1$.

Alternatively, we can slightly modify the the prime factorization code above.

1#include <bits/stdc++.h>
2using namespace std;
3
4int max_div[1000001];
5
6int main() {
7    ios_base::sync_with_stdio(0);
8    cin.tie(0);
9    for (int i = 2; i <= 1000000; i++) {
10        if (!max_div[i]) {

1import java.io.*;
2import java.util.*;
3
4public class Main {
5    static int solve(int n) {
6        int divisors = 1;
7        for (int i = 2; i * i <= n; i++) {
8            int ct = 0;
9            while (n % i == 0) {
10                ct++;

GCD & LCM

GCD

The greatest common divisor (GCD) of two integers $a$ and $b$ is the largest integer that is a factor of both $a$ and $b$. In order to find the GCD of two non-negative integers, we use the Euclidean Algorithm, which is as follows:

This algorithm is very easy to implement using a recursive function, as follows:

1public int gcd(int a, int b){
2    if (b == 0) return a;
3    return gcd(b, a % b);
4}

1int gcd(int a, int b){
2    if (b == 0) return a;
3    return gcd(b, a % b);
4}

1def gcd(a, b):
2    if b == 0:
3        return a
4    return gcd(b, a % b)

This function runs in $\mathcal{O}(\log ab)$ time because $a\le b⟹b\%a<\frac{b}{2}$.

The worst-case scenario for the Euclidean algorithm is when $a$ and $b$ are consecutive Fibonacci numbers $F_n$ and $F_{n+1}$. for an explanation). In this case, the algorithm will calculate $\gcd (F_n,F_{n+1})=\gcd (F_{n-1},F_n)=\cdots =\gcd (0,F_1)$. This means that finding $\gcd (F_n,F_{n+1})$ takes $n+1$ steps, which is proportional to $\log \left(F_n{F}_{n+1}\right)$.

LCM

The least common multiple (LCM) of two integers $a$ and $b$ is the smallest integer divisible by both $a$ and $b$. The LCM can easily be calculated from the following property with the GCD:

If we want to take the GCD or LCM of more than two elements, we can do so two at a time, in any order. For example,

Exercise: What's wrong with the following code?

1ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b,a%b); }
2ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }
3
4int main() { cout << lcm(1000000000,999999999); } // output: 1808348672

Problems