These are the notes for Competitive Programming episode 27 (number theory 5). Twelve dancers in a Navratri Garba circle pass one dandiya stick k places at a time, and only the step sizes 1, 5, 7 and 11 reach everyone: exactly the k that share no factor with 12. Counting them is Euler's totient φ(n). We meet an original problem, Garba Steps, where a gcd loop gets Time Limit Exceeded on n = 10^12, turn episode 24's complement counting into the formula φ(n) = n · Π(1 − 1/p), watch a stress test catch a floating-point bug at n = 451, and fix it with whole numbers. Then the phi sieve answers 10^5 queries of a second original problem, Fraction Flashcards, and the prime exponents give the number of divisors d(n) and the sum of divisors σ(n), with a divisor sieve for a third problem, Parade Rows. Three real bugs close the episode. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hooks
The Garba circle. 12 dancers, numbered 0 to 11, stand in a circle. A dandiya stick starts with dancer 0 and moves k places forward every beat. With k = 5 it visits 0, 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7 and every dancer gets a turn. With k = 4 it goes 0, 4, 8, 0 … and only 3 dancers ever hold it. The stick returns to dancer 0 after 12 / gcd(k, 12) passes, so it reaches everyone exactly when gcd(k, 12) = 1. Out of the 12 step sizes, 4 work: 1, 5, 7, 11.
Fraction flashcards. A maths teacher makes one flashcard per fraction a/b with 0 < a < b ≤ n. But 1/2 and 2/4 are the same fraction, so only fractions in lowest terms get a card. For n = 4: 1/2, 1/3, 2/3, 1/4, 3/4, so 5 cards.
PT period and the thali. The PT teacher puts 36 students in equal rows: 1 × 36, 2 × 18, 3 × 12, 4 × 9, 6 × 6, 9 × 4, 12 × 3, 18 × 2, 36 × 1. Each arrangement is a divisor of 36. Counting them is like counting thalis: choose 0, 1 or 2 rotis and 0, 1 or 2 sweets, and there are 3 · 3 = 9 different plates. 36 = 2² · 3², and every divisor chooses how many 2s (0 to 2) and how many 3s (0 to 2).
Coprime numbers and φ(n)
Two numbers are coprime when their gcd (greatest common divisor, episode 19) is 1: they share no factor except 1. 5 and 12 are coprime; 4 and 12 are not (both are even).
Euler's totient φ(n) (φ is the Greek letter phi) is the number of k in 1 … n with gcd(k, n) = 1.
| n | coprime k | φ(n) |
|---|---|---|
| 1 | 1 | 1 |
| 7 | 1 2 3 4 5 6 | 6 |
| 12 | 1 5 7 11 | 4 |
| 36 | 1 5 7 11 13 17 19 23 25 29 31 35 | 12 |
| k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| gcd(k, 12) | 1 | 2 | 3 | 4 | 1 | 6 | 1 | 4 | 3 | 2 | 1 | 12 |
Problem E · Garba Steps
Problem E · Garba Steps (written for this course). There are t Garba circles. A circle has n dancers. A step size k (1 ≤ k ≤ n) is good if passing the stick k places at a time reaches every dancer. For each circle, print the number of good step sizes, which is φ(n).
Input:
t, then t lines withn.1 ≤ t ≤ 100,1 ≤ n ≤ 10^12, time limit 2 seconds.
| Sample input | Sample output |
|---|---|
4 / 12 / 7 / 1 / 36 |
4 / 6 / 1 / 12 |
Brute force: a gcd for every k (Time Limit Exceeded)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
ll cnt = 0;
for (ll k = 1; k <= n; k++)
if (gcd(k, n) == 1) cnt++;
cout << cnt << "\n";
}
return 0;
}
| Input | Output |
|---|---|
| the sample | 4 6 1 12 |
1 / 999999999989 (a prime) |
Time Limit Exceeded |
Why: 10^12 gcd calls for one circle, and there can be 100 circles.
The key observation: count the complement (episode 24)
A step k is bad when it shares a prime factor with n. For 12 = 2 · 2 · 3, bad means divisible by 2 or by 3. Inclusion-exclusion: 6 multiples of 2, 4 multiples of 3, 2 multiples of 6, so bad = 6 + 4 − 2 = 8 and good = 12 − 8 = 4.
For two primes p and q of n:
n − n/p − n/q + n/(pq) = n · (1 − 1/p) · (1 − 1/q)
The same factoring works for any number of primes, which gives
φ(n) = n · Π (1 − 1/p) over the distinct primes p of n
(Π, capital pi, means "multiply all of them".)
- φ(12) = 12 · 1/2 · 2/3 = 4.
- A prime p: φ(p) = p − 1 (only p itself is bad). φ(7) = 6.
- A prime power: φ(p^k) = p^k − p^(k−1). φ(8) = 4, φ(9) = 6.
- Exponents don't matter, only which primes appear: φ(36) = 36 · 1/2 · 2/3 = 12.
The distinct primes of n come from episode 20's trial division up to √n: for n = 10^12 that is 10^6 steps instead of 10^12.
First attempt: the formula with a double
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll phi(ll n) {
double f = 1; // product of (1 - 1/p)
ll m = n;
for (ll p = 2; p * p <= m; p++)
if (m % p == 0) {
f *= 1 - 1.0 / p;
while (m % p == 0) m /= p;
}
if (m > 1) f *= 1 - 1.0 / m;
return (ll)(n * f);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
cout << phi(n) << "\n";
}
return 0;
}
Real outputs: the sample gives 4 6 1 12, all correct. But a stress test finds a problem.
A stress test catches the bug
Episode 5's recipe: compare the trusted slow answer with the fast one on many small inputs.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(ll n) {
ll c = 0;
for (ll k = 1; k <= n; k++)
if (gcd(k, n) == 1) c++;
return c;
}
ll phi(ll n) {
double f = 1; // product of (1 - 1/p)
ll m = n;
for (ll p = 2; p * p <= m; p++)
if (m % p == 0) {
f *= 1 - 1.0 / p;
while (m % p == 0) m /= p;
}
if (m > 1) f *= 1 - 1.0 / m;
return (ll)(n * f);
}
int main() {
for (ll n = 1; n <= 1000; n++) {
ll b = brute(n), f = phi(n);
if (b != f) {
cout << "n=" << n << " brute=" << b << " fast=" << f;
return 0;
}
}
cout << "all 1000 tests passed";
}
Real output:
n=451 brute=400 fast=399
451 = 11 · 41, so φ(451) = 451 · 10/11 · 40/41 = 10 · 40 = 400. Why 399? 1 − 1/11 = 0.909090… repeats forever, and a double keeps only about 16 significant digits, so the product is a hair too small. This program shows it:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
double f = (1 - 1.0 / 11) * (1 - 1.0 / 41);
cout << setprecision(17) << 451 * f << "\n";
cout << (ll)(451 * f) << "\n";
}
Real output:
399.99999999999994
399
Converting a double to long long does not round, it truncates (chops the decimals), so 399.99999999999994 becomes 399.
The fix: stay in whole numbers
Start with ans = n and for each distinct prime p do ans = ans / p * (p - 1). Divide first. The division is always exact: at that moment ans equals (n with the earlier primes removed once each) times their (q − 1) factors, and p still divides it. For 12: 12 / 2 · 1 = 6, then 6 / 3 · 2 = 4. Dividing first also keeps the numbers small (ans * (p - 1) / p is exact too, but the middle value can be p times bigger). ans -= ans / p is the same step written differently.
With the whole-number phi the same stress test prints all 1000 tests passed.
The accepted solution (O(√n) per number)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll phi(ll n) {
ll ans = n;
for (ll p = 2; p * p <= n; p++)
if (n % p == 0) {
ans = ans / p * (p - 1); // divide first
while (n % p == 0) n /= p;
}
if (n > 1) ans = ans / n * (n - 1); // leftover prime
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
ll n;
cin >> n;
cout << phi(n) << "\n";
}
return 0;
}
| Input | Output |
|---|---|
4 / 12 7 1 36 (one per line) |
4 6 1 12 |
4 / 13 1024 999999999989 1000000000000 |
12 512 999999999988 400000000000 |
1 / 451 |
400 |
100 / 999999999989 100 times (worst case) |
100 × 999999999988 in about 0.37 s |
n > 1 after the loop means one prime larger than √n is left (n can have at most one such prime). 13 is prime: 12. 1024 = 2^10: 512. 10^12 = 2^12 · 5^12: 10^12 · 1/2 · 4/5 = 400000000000.
Problem E2 · Fraction Flashcards
Problem E2 · Fraction Flashcards (written for this course). For each query n, count the fractions a/b in lowest terms with 0 < a < b ≤ n.
Input:
q, then q lines withn.1 ≤ q ≤ 10^5,1 ≤ n ≤ 10^6, time limit 2 seconds.
| Sample input | Sample output |
|---|---|
3 / 4 / 10 / 1 |
5 / 31 / 0 |
a/b is in lowest terms exactly when gcd(a, b) = 1, so denominator b has φ(b) cards and the answer is φ(2) + φ(3) + … + φ(n). For n = 10: 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 31. (These fractions, with 0/1 and 1/1, form the Farey sequence of order n.)
Brute force: trial division for every denominator, every query
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll phi(ll n) {
ll ans = n;
for (ll p = 2; p * p <= n; p++)
if (n % p == 0) {
ans = ans / p * (p - 1); // divide first
while (n % p == 0) n /= p;
}
if (n > 1) ans = ans / n * (n - 1); // leftover prime
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
ll sum = 0;
for (int b = 2; b <= n; b++) sum += phi(b);
cout << sum << "\n";
}
return 0;
}
Sample: 5 31 0. Twenty queries with n = 1000000: Time Limit Exceeded. Each query redoes a million trial divisions, and the same φ values are computed again and again.
The phi sieve
Like the sieve of Eratosthenes (episode 20): start with phi[i] = i. Walk p upward; if phi[p] == p, no smaller prime has touched p, so p is prime. Then for every multiple j of p do phi[j] -= phi[j] / p, which is "times (1 − 1/p)", exact for the same reason as before. Each number gets one step for each of its distinct primes.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| start | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| after p = 2 | 1 | 1 | 3 | 2 | 5 | 3 | 7 | 4 | 9 | 5 | 11 | 6 |
| φ(n) (after 3, 5, 7, 11) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
Work: N/2 + N/3 + N/5 + … over the primes = O(N log log N), about 3·10^6 steps for N = 10^6. Then a prefix sum (episode 7) pre[n] = pre[n − 1] + phi[n] answers each query in O(1). The arrays are global so 10^6 entries don't overflow the stack (episode 20).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000000;
int phi[N + 1];
ll pre[N + 1]; // phi(2) + ... + phi(n)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 0; i <= N; i++) phi[i] = i;
for (int p = 2; p <= N; p++)
if (phi[p] == p) // untouched: prime
for (int j = p; j <= N; j += p)
phi[j] -= phi[j] / p;
for (int n = 2; n <= N; n++) pre[n] = pre[n - 1] + phi[n];
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
cout << pre[n] << "\n";
}
return 0;
}
| Input | Output |
|---|---|
3 / 4 / 10 / 1 |
5 31 0 |
4 / 4 / 10 / 1 / 1000000 |
5 31 0 303963552391 |
100000 queries, all 1000000 |
100000 × 303963552391 in about 0.03 s |
Number of divisors d(n) and sum of divisors σ(n)
Write n with its prime factorisation (episode 20): n = p1^e1 · p2^e2 · … A divisor picks an exponent from 0 to e1 for p1, from 0 to e2 for p2, and so on, so
d(n) = (e1 + 1) · (e2 + 1) · … number of divisors
σ(n) = (1 + p1 + … + p1^e1) · (1 + p2 + … + p2^e2) · … sum of divisors
Expanding the brackets of σ produces every divisor exactly once.
- 36 = 2² · 3²: d = 3 · 3 = 9, σ = (1 + 2 + 4)(1 + 3 + 9) = 7 · 13 = 91 = 1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 + 36.
- 360 = 2³ · 3² · 5: d = 4 · 3 · 2 = 24, σ = 15 · 13 · 6 = 1170.
- A prime p: d = 2, σ = p + 1.
One number up to 10^12: trial division with exponents
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n;
cin >> n;
ll d = 1, s = 1;
for (ll p = 2; p * p <= n; p++) {
if (n % p) continue;
int e = 0;
ll pk = 1, sum = 1; // 1 + p + ... + p^e
while (n % p == 0) {
n /= p;
e++;
pk *= p;
sum += pk;
}
d *= e + 1;
s *= sum;
}
if (n > 1) { // leftover prime, e = 1
d *= 2;
s *= n + 1;
}
cout << d << " " << s << "\n";
return 0;
}
| Input | Output |
|---|---|
36 |
9 91 |
360 |
24 1170 |
1 |
1 1 |
999999999989 |
2 999999999990 |
1000000000000 |
169 2499694822171 (2^12 · 5^12: 13 · 13 divisors) |
Problem E3 · Parade Rows (the divisor sieve)
Problem E3 · Parade Rows (written for this course). For each query x, print d(x), the number of ways to stand x students in equal rows, and σ(x), the sum of all divisors of x.
Input:
q, then q lines withx.1 ≤ q ≤ 10^5,1 ≤ x ≤ 10^6.
Flip the question: instead of finding the divisors of each j, let every i visit its multiples i, 2i, 3i … (i divides each of them) and add 1 to d[j] and i to sigma[j]. The work is N/1 + N/2 + … + N/N ≈ N ln N ≈ 1.4·10^7 for N = 10^6: O(N log N) (a harmonic sum).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000000;
int d[N + 1];
ll sigma[N + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j += i) { // i divides j
d[j]++;
sigma[j] += i;
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
cout << d[x] << " " << sigma[x] << "\n";
}
return 0;
}
| Input | Output |
|---|---|
5 / 36 / 360 / 1 / 999983 / 1000000 |
9 91 / 24 1170 / 1 1 / 2 999984 / 49 2480437 in about 0.1 s |
Complexity vs the constraints
| Approach | Time | Worst case here | Verdict |
|---|---|---|---|
| gcd for every k | O(n log n) per number | 10^12 per circle | TLE |
| Totient formula + trial division | O(√n) per number | 100 · 10^6 | ≈ 0.37 s |
| Brute Σφ per query | O(n √n) per query | 10^5 queries | TLE |
| Phi sieve + prefix sums | O(N log log N + q) | ≈ 3·10^6 + 10^5 | ≈ 0.03 s |
| d and σ by trial division | O(√n) per number | 10^6 | instant |
| Divisor sieve | O(N log N + q) | ≈ 1.4·10^7 | ≈ 0.1 s |
The rule: one big number (up to 10^12 or so): trial division in O(√n). Many numbers up to about 10^7: sieve once, then look up.
Common mistakes (and the real outputs)
Bug 1: forgetting the leftover prime
The accepted solution without the line if (n > 1) ans = ans / n * (n - 1);. Input 3 / 14 / 13 / 12. Real output: 7 13 6 (expected 6 12 4). 14 = 2 · 7 and 7 > √14, so the loop never sees 7. A prime n is never touched at all. Even 12 fails: after dividing out the 2s, n = 3 and the loop stops because 3 · 3 > 3.
Bug 2: the formula in integers
ans = ans * (1 - 1 / p); // the formula
...
if (n > 1) ans = ans * (1 - 1 / n);
The sample gives 12 7 1 36: it prints n itself. With integers, 1 / p is 0, so every step multiplies by 1.
Bug 3: the floating-point formula
f *= 1 - 1.0 / p; … return (ll)(n * f); gives 399 for n = 451 (expected 400), because 399.99999999999994 is truncated. The samples pass, only the stress test finds it.
Bug 4: an int prefix sum
int pre[N + 1]; // phi(2) + ... + phi(n)
Input 4 / 4 / 10 / 1 / 1000000. Real output: 5 31 0 -979125625 (expected 303963552391). The sum is about 3·10^11 and an int holds at most about 2.1·10^9, so it overflows and wraps. Use long long.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
f *= 1 - 1.0 / p; then (ll)(n * f) |
φ(451) = 399 (expected 400) |
399.99999999999994 truncated | ans = ans / p * (p - 1) |
no if (n > 1) after the loop |
7 13 6 (expected 6 12 4) |
the prime above √n is missed | handle the leftover n |
ans = ans * (1 - 1 / p); |
prints n (12 7 1 36) |
1 / p is 0 in integers | divide first, then × (p − 1) |
int pre[N + 1]; |
-979125625 |
≈ 3·10^11 overflows int | ll pre[N + 1] |
for (ll k = 1; k <= n; k++) gcd(k, n) |
Time Limit Exceeded | 10^12 gcds | formula + trial division |
Mini project
Build a small number-theory toolkit and test it against brute force: phi(n) by trial division, phiSieve(N), divisorCount(n) and divisorSum(n) by trial division, and divisorSieve(N). Stress test each one against a direct loop for every n ≤ 2000. Then print a table for n = 1 … 30 with n, φ(n), d(n) and σ(n), and mark the primes (d = 2) and the perfect numbers (σ = 2n).
Practice
These follow the video's homework.
-
Count the pairs (a, b) with 1 ≤ a, b ≤ n and gcd(a, b) = 1. Example: n = 4 and n = 10.
Answer
The pairs with a < b are exactly the flashcards (a/b in lowest terms), so there are φ(2) + … + φ(n) of them; the pairs with a > b are the mirror images; and (1, 1) is the only pair with a = b. Answer = 2 · (φ(1) + … + φ(n)) − 1. n = 4: 2 · 6 − 1 = <b>11</b>. n = 10: 2 · 32 − 1 = <b>63</b> (both checked by brute force). -
Compute gcd(1, n) + gcd(2, n) + … + gcd(n, n) for n up to 10^12. Example: n = 12.
Answer
Group the k by g = gcd(k, n). gcd(k, n) = g means k = g · m with gcd(m, n/g) = 1, so there are φ(n/g) such k. Sum = Σ over divisors g of n of g · φ(n/g). For n = 12: 1·4 + 2·2 + 3·2 + 4·2 + 6·1 + 12·1 = <b>40</b>. For n up to 10^12, the sum is multiplicative: each prime power p^e contributes (e + 1)·p^e − e·p^(e−1), so one trial division is enough. 12 = 2² · 3: (3·4 − 2·2)(2·3 − 1) = 8 · 5 = 40. Also checked: n = 36 → 168, n = 100 → 520. -
Find every perfect number up to 10^6 (σ(n) = 2n).
Answer
Run the divisor sieve and test sigma[n] == 2 * n: <b>6, 28, 496, 8128</b> (checked). -
Which x ≤ 10^6 has the most divisors?
Answer
The maximum is <b>240</b> divisors, first reached by <b>720720</b> = 2^4 · 3^2 · 5 · 7 · 11 · 13 ((4+1)(2+1)·2·2·2·2 = 240). 831600, 942480, 982800 and 997920 also have 240 (checked with the divisor sieve). -
Without code: φ(100) and φ(1000).
Answer
Both have the primes 2 and 5: φ(100) = 100 · 1/2 · 4/5 = <b>40</b>, φ(1000) = 1000 · 1/2 · 4/5 = <b>400</b> (checked by brute force).
Quick quiz
What is φ(30)? (30 = 2 · 3 · 5.)
A) 15 · B) 8 · C) −1 · D) 10
Answer
B. 30 · 1/2 · 2/3 · 4/5 = 8: the numbers 1, 7, 11, 13, 17, 19, 23, 29 (checked by brute force). A, 15, only used the prime 2. C, −1, is 30 − 15 − 10 − 6: it subtracted the three groups without adding back the overlaps.
Interview questions
- What does φ(n) count? The integers k in 1 … n with gcd(k, n) = 1.
- Give the formula and where it comes from. φ(n) = n · Π(1 − 1/p) over the distinct primes of n; it is inclusion-exclusion on "divisible by p" for the primes of n, factored into a product.
- How do you compute φ(n) for n ≤ 10^12? Trial division up to √n with
ans = ans / p * (p - 1)for each distinct prime, plus the leftover prime if n > 1 at the end. O(√n). - Why avoid doubles in the formula? 1 − 1/p is not exact in binary; the product can land just below an integer and the cast truncates (φ(451) came out as 399).
- How do you get φ for every n ≤ 10^6? The phi sieve:
phi[i] = i, and for each prime p,phi[j] -= phi[j] / pfor all multiples j. O(N log log N). - How many divisors does n = Π p^e have, and what is their sum? d(n) = Π(e + 1), σ(n) = Π(1 + p + … + p^e).
- Why is the divisor sieve O(N log N)? Each i visits N / i multiples, and N/1 + N/2 + … + N/N ≈ N ln N.
- How many fractions in lowest terms lie strictly between 0 and 1 with denominator ≤ n? φ(2) + … + φ(n); it needs
long long(about 3·10^11 for n = 10^6).
Glossary
| Term | Meaning | Example |
|---|---|---|
| gcd | Greatest common divisor | gcd(4, 12) = 4 |
| Coprime | Sharing no factor except 1; gcd = 1 | 5 and 12 |
| Euler's totient φ(n) | How many k in 1 … n are coprime to n | φ(12) = 4 |
| Distinct primes | The different primes dividing n, each once | 36 → 2, 3 |
| Exponent | How many times a prime divides n | 360 = 2³ · 3² · 5 |
| Π (capital pi) | Multiply all the terms | Π(1 − 1/p) |
| Complement | Count the opposite and subtract from the total | good = 12 − 8 |
| Trial division | Trying divisors 2, 3, … up to √n | primes of 10^12 in 10^6 steps |
| Leftover prime | The one prime above √n that remains after the loop | 14 → 7 |
| Truncation | Converting a double to an integer by chopping the decimals | 399.99999999999994 → 399 |
| Stress test | Comparing a fast solution with a brute force on many small inputs | n=451 brute=400 fast=399 |
| Phi sieve | Computing φ for all n ≤ N by visiting multiples of each prime | phi[j] -= phi[j] / p |
| Prefix sum | pre[n] = sum of the first n values; any total in O(1) | pre[10] = 31 |
| Lowest terms | A fraction whose top and bottom are coprime | 1/2, not 2/4 |
| Farey sequence | All fractions in lowest terms in [0, 1] with denominator ≤ n | 0/1 1/2 1/1 for n = 2 |
| Divisor | A number that divides n exactly | 9 divides 36 |
| d(n) | Number of divisors | d(36) = 9 |
| σ(n) (sigma) | Sum of divisors | σ(36) = 91 |
| Perfect number | σ(n) = 2n | 6, 28 |
| Divisor sieve | Each i adds itself to all its multiples | sigma[j] += i |
| Harmonic sum | N/1 + N/2 + … + N/N ≈ N ln N | 1.4·10^7 for N = 10^6 |
| Integer overflow | A value too big for its type wraps around | int sum → -979125625 |
Summary
- φ(n) counts the k ≤ n coprime to n. In a circle of n, step k reaches everyone exactly when gcd(k, n) = 1.
- Complement + inclusion-exclusion over the primes gives φ(n) = n · Π(1 − 1/p). Exponents don't matter.
- Compute it with whole numbers,
ans = ans / p * (p - 1), by trial division in O(√n), and don't forget the leftover prime. Doubles gave φ(451) = 399. - For all n ≤ N: the phi sieve in O(N log log N), with prefix sums in
long longfor Σφ (303963552391 for N = 10^6). - d(n) = Π(e + 1) and σ(n) = Π(1 + p + … + p^e); for all n ≤ N the divisor sieve runs in O(N log N).
- Real bugs: no leftover prime (
7 13 6), the formula in integers (prints n), anintprefix sum (-979125625), doubles (399).
Solutions in C++, Java and Python
Problem E · Garba Steps
C++: the accepted solution above.
Java (tested: the sample → 4 6 1 12; 13 1024 999999999989 1000000000000 → 12 512 999999999988 400000000000; 100 × 999999999989 in about 0.4 s):
import java.io.*;
import java.util.*;
public class Main {
static long phi(long n) {
long ans = n;
for (long p = 2; p * p <= n; p++)
if (n % p == 0) {
ans = ans / p * (p - 1); // divide first
while (n % p == 0) n /= p;
}
if (n > 1) ans = ans / n * (n - 1); // leftover prime
return ans;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
long n = Long.parseLong(br.readLine().trim());
sb.append(phi(n)).append('\n');
}
System.out.print(sb);
}
}
Python (same tests, all match). Python runs about 10^6 loop steps per 0.1 s, so the worst case of 100 primes near 10^12 takes about 8 s here: correct, but use C++ or Java for that limit.
import sys
def phi(n):
ans = n
p = 2
while p * p <= n:
if n % p == 0:
ans = ans // p * (p - 1) # divide first
while n % p == 0:
n //= p
p += 1
if n > 1: # leftover prime
ans = ans // n * (n - 1)
return ans
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
print("\n".join(str(phi(int(x))) for x in data[1:1 + t]))
main()
Problem E2 · Fraction Flashcards
C++: the phi-sieve program above.
Java (tested: 4 10 1 1000000 → 5 31 0 303963552391; 100000 queries in about 0.3 s):
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
final int N = 1000000;
int[] phi = new int[N + 1];
long[] pre = new long[N + 1]; // phi(2) + ... + phi(n)
for (int i = 0; i <= N; i++) phi[i] = i;
for (int p = 2; p <= N; p++)
if (phi[p] == p) // untouched: prime
for (int j = p; j <= N; j += p)
phi[j] -= phi[j] / p;
for (int n = 2; n <= N; n++) pre[n] = pre[n - 1] + phi[n];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
int n = Integer.parseInt(br.readLine().trim());
sb.append(pre[n]).append('\n');
}
System.out.print(sb);
}
}
Python (same tests, about 0.3 s for 100000 queries). A pure-Python phi sieve is slow, so this version builds a smallest-prime-factor table with slice assignment (largest primes first, so the smallest prime is written last) and uses φ(i) = φ(i/p) · p if p still divides i/p, else φ(i/p) · (p − 1).
import sys
from itertools import accumulate
N = 10**6
def main():
# smallest prime factor: descending primes, so the smallest one writes last
spf = [0] * (N + 1)
for p in range(1000, 1, -1):
if all(p % d for d in range(2, int(p ** 0.5) + 1)):
spf[p * p::p] = [p] * len(range(p * p, N + 1, p))
phi = [0] * (N + 1)
phi[1] = 1
for i in range(2, N + 1):
p = spf[i] or i # 0 means i is prime
m = i // p
phi[i] = phi[m] * (p if m % p == 0 else p - 1)
phi[1] = 0 # denominators start at 2
pre = list(accumulate(phi))
data = sys.stdin.buffer.read().split()
q = int(data[0])
print("\n".join(str(pre[int(x)]) for x in data[1:1 + q]))
main()
Problem E3 · Parade Rows
C++: the divisor-sieve program above.
Java (tested: 36 360 1 999983 1000000 → 9 91, 24 1170, 1 1, 2 999984, 49 2480437; 100000 queries in about 0.3 s):
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
final int N = 1000000;
int[] d = new int[N + 1];
long[] sigma = new long[N + 1];
for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j += i) { // i divides j
d[j]++;
sigma[j] += i;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
int x = Integer.parseInt(br.readLine().trim());
sb.append(d[x]).append(' ').append(sigma[x]).append('\n');
}
System.out.print(sb);
}
}
Python (same tests, about 0.2 s for 100000 queries). Instead of the O(N log N) double loop, which is slow in Python, it factorises each x with a smallest-prime-factor table and applies d = Π(e + 1), σ = Π(1 + p + … + p^e).
import sys
N = 10**6
def main():
spf = [0] * (N + 1)
for p in range(1000, 1, -1):
if all(p % d for d in range(2, int(p ** 0.5) + 1)):
spf[p * p::p] = [p] * len(range(p * p, N + 1, p))
data = sys.stdin.buffer.read().split()
q = int(data[0])
out = []
for x in map(int, data[1:1 + q]):
d, s = 1, 1
while x > 1:
p = spf[x] or x # 0 means x is prime
e, pk, total = 0, 1, 1
while x % p == 0:
x //= p
e += 1
pk *= p
total += pk # 1 + p + ... + p^e
d *= e + 1
s *= total
out.append(f"{d} {s}")
print("\n".join(out))
main()