Rare
0/9

# Divisibility

Authors: Darren Yao, Michael Cao, Andi Qu, and Kevin Sheng

Using the information that one integer evenly divides another.

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

Resources
AoPS

practice problems, set focus to number theory!

AoPS

good book

## Resources

Resources
IUSACO

module is based off this

David Altizio
CPH
PAPS
MONT
Sato

nice proofs and problems

## Prime Factorization

Focus Problem – read through this problem before continuing!

A positive integer $a$ is called a divisor or a factor of a non-negative integer $b$ if $b$ is divisible by $a$, which means that there exists some integer $k$ such that $b = ka$. An integer $n > 1$ is prime if its only divisors are $1$ and $n$. Integers greater than $1$ that are not prime are composite.

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

$n = {p_1}^{a_1} {p_2}^{a_2} \cdots {p_k}^{a_k}$

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 any positive integer.

C++

vector<int> factor(int n) {	vector<int> ret;	for (int i = 2; i * i <= n; i++) {		while (n % i == 0) {			ret.push_back(i);			n /= i;		}	}	if (n > 1) ret.push_back(n);	return ret;}

Java

ArrayList<Integer> factor(int n) {	ArrayList<Integer> factors = new ArrayList<>();	for (int i = 2; i * i <= n; i++) {		while (n % i == 0) {			factors.add(i);			n /= i;		}	}	if (n > 1) factors.add(n);	return factors;}

Python

def factor(n):	ret = []	i = 2	while i * i <= n:		while n % i == 0:			ret.append(i)			n //= i		i += 1	if n > 1:		ret.append(n)	return ret

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$.

$i$$n$$v$
$2$$252$$\{\}$
$2$$126$$\{2\}$
$2$$63$$\{2, 2\}$
$3$$21$$\{2, 2, 3\}$
$3$$7$$\{2, 2, 3, 3\}$

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.

C++

#include <iostream>
using namespace std;
int main() {	int n;	cin >> n;	for (int q = 0; q < n; q++) {		int x;		int div_num = 0;

Java

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;
public class Divisors {	public static void main(String[] args) throws IOException {		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));		int queryNum = Integer.parseInt(read.readLine());		StringBuilder ans = new StringBuilder();		for (int q = 0; q < queryNum; q++) {

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. Consider:

$x = {p_1}^{a_1} {p_2}^{a_2} \cdots {p_k}^{a_k}$

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 \leq 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.

C++

#include <iostream>
using namespace std;
const int MAX_N = 1e6;// max_div[i] contains the largest prime that goes into iint max_div[MAX_N + 1];
int main() {	for (int i = 2; i <= MAX_N; i++) {

Java

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;
public class Divisors {	private static final int MAX_N = (int) Math.pow(10, 6);	public static void main(String[] args) throws IOException {		// maxDiv[i] contains the largest prime that can divide i		int[] maxDiv = new int[MAX_N + 1];		for (int i = 2; i <= MAX_N; i++) {

Python

MAX_N = 10 ** 6
# max_div[i] contains the largest prime that can go into imax_div = [0 for _ in range(MAX_N + 1)]for i in range(2, MAX_N + 1):	if max_div[i] == 0:		for j in range(i, MAX_N + 1, i):			max_div[j] = i
ans = []

### Optional

Apply the linear sieve.

## 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:

$\gcd(a, b) = \begin{cases} a & b = 0 \\ \gcd(b, a \bmod b) & b \neq 0 \\ \end{cases}$

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

Java

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

C++

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

For C++14, you can use the built-in __gcd(a,b).

In C++17, there exists std::gcd and std::lcm in the <numeric> header, so there's no need to code your own GCD and LCM if you're using that.

Python

def gcd(a, b):	return a if b == 0 else gcd(b, a % b)

This function runs in $\mathcal{O}(\log ab)$ time because $a\le b \implies b\pmod 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) = \dots = \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:

$\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}=\frac{a}{\gcd(a,b)}\cdot b.$

### Warning!

Coding $\text{lcm}$ as a * b / gcd(a, b) might cause integer overflow if the value of a * b is greater than the max size of the data type of a * b (e.g. the max size of int is around 2 billion). Dividng a by gcd(a, b) first, then multiplying it by b will prevent integer overflow if the result fits in an int.

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,

$\gcd(a_1, a_2, a_3, a_4) = \gcd(a_1, \gcd(a_2, \gcd(a_3, a_4))).$

## Problems

StatusSourceProblem NameDifficultyTags
ACEasy
Show TagsPrime Factorization
CFEasy
Show TagsDivisibility, Modular Arithmetic
CFEasy
Show TagsNT
CFEasy
Show TagsDivisibility
CSESNormal
CFNormal
Show TagsPrime Factorization
CSESHard
CFHard
Show TagsDivisibility

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!