Divisibility
Authors: Darren Yao, Michael Cao, Andi Qu, Kevin Sheng
Contributor: Juheon Rhee
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 | ||||
AoPS | nice proofs and problems |
Prime Factorization
A positive integer is called a divisor or a factor of a non-negative integer if is divisible by , which means that there exists some integer such that . An integer is prime if its only divisors are and . Integers greater than 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:
where the are distinct primes and the 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
List<Integer> factor(int n) {List<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
from typing import Listdef factor(n: int) -> List[int]:ret = []i = 2while i * i <= n:while n % i == 0:ret.append(i)n //= ii += 1if n > 1:ret.append(n)return ret
This algorithm runs in time, because the for loop checks divisibility for at most values. Even though there is a while loop inside the for loop, dividing by quickly reduces the value of , 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 .
At this point, the for loop terminates, because is already 3 which is greater than . In the last step, we add to the list of factors , because it otherwise won't be added, for a final prime factorization of .
Focus Problem – try your best to solve this problem before continuing!
Solution - Counting Divisors
The most straightforward solution is just to do what the problem asks us to do - for each , find the number of divisors of in 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();
Python
Warning!
Due to Python's big constant factor, the following code TLEs on quite a few test cases.
ans = []for _ in range(int(input())):div_num = 0x = int(input())i = 1while i * i <= x:if x % i == 0:div_num += 1 if i**2 == x else 2i += 1ans.append(div_num)print("\n".join(str(i) for i in ans))
This solution runs in time, which is just fast enough to get AC. However, we can actually speed this up to get an solution!
First, let's discuss an important property of the prime factorization. Consider:
Then the number of divisors of is simply .
Why is this true? The exponent of in any divisor of must be in the range and each different exponent results in a different set of divisors, so each contributes to the product.
can have distinct prime factors, so if we can find the prime factorization of efficiently, we can use it with the above property to answer queries in time instead of the previous time.
Here's how we find the prime factorization of in time with preprocessing:
- For each , find any prime number that divides . To find this, we can use the Sieve of Eratosthenes which runs in , where is the larger numbers we consider. There's also a version of the sieve that runs in linear time, but we won't be needing it.
- We can find the prime factorization of by repeatedly dividing it by the prime numbers we calculated earlier until .
Using this method gives us the following code:
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 iint[] 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] = ians = []
GCD & LCM
GCD
The greatest common divisor (GCD) of two integers and is the largest integer that is a factor of both and . In order to find the GCD of two non-negative integers, we use the Euclidean Algorithm, which is as follows:
This algorithm can be implemented with 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 version.
Python
def gcd(a: int, b: int) -> int:return a if b == 0 else gcd(b, a % b)
You won't have to actually implement this in-contest,
as the built-in math
library has a gcd
and lcm
function.
This function runs in time because .
The worst-case scenario for the Euclidean algorithm is when and are consecutive Fibonacci numbers and . In this case, the algorithm will calculate that . This takes a total of calls, which is proportional to .
LCM
The least common multiple (LCM) of two integers and is the smallest integer divisible by both and . The LCM can be calculated with the GCD using this property:
Warning!
Coding 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
in C++ and Java 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
.
Also, these two functions are associative, meaning that 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,
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
AC | Easy | Show TagsPrime Factorization | |||
CF | Easy | Show TagsDivisibility, Modular Arithmetic | |||
Kilonova | Normal | Show TagsMath, Prime Factorization | |||
CF | Easy | Show TagsNT | |||
CF | Easy | Show TagsDivisibility | |||
CSES | Normal | ||||
CF | Normal | Show TagsPrime Factorization | |||
CC | Normal | Show TagsDivisibility | |||
CSES | Hard | ||||
CF | Hard | Show TagsDivisibility |
Module Progress:
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!