These problems look like loops over 10¹² numbers or 2ⁿ strings. Each one gives way to a fact about whole numbers: a carry stops at the first digit below 9, a finite map must loop, a divisor counts its multiples, n / d takes few values, and a prime modulus makes every number invertible. Twelve moves, fifteen problems.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.
Add from the last digit. A 9 becomes 0 and hands its 1 to the left; the first digit below 9 takes the 1, and nothing to its left changes, so the function returns there. Only an array of 9s gets a new digit in front.
plusOne([9, 9])?
Both 9s become 0 and pass the 1 left. The loop ends with the carry still owed, so a 1 goes in front: 99 + 1 = 100.
Why can the loop return as soon as a digit is below 9?
A digit d below 9 becomes d + 1, at most 9, so it makes no 10 and passes nothing on. Every digit to its left keeps its value.
A number too long for any integer type is given as an array of digits. Add one to it.
Add the way it is done on paper, from the last digit. A digit below 9 takes the 1 and nothing carries past it, so the answer is ready. A 9 becomes 0 and passes the 1 to the digit on its left. If every digit was 9, the carry falls off the front, and the answer is a 1 followed by zeros, one digit longer.
vector<int> plusOne(vector<int>& digits) { for (int i = (int)digits.size() - 1; i >= 0; i--) { if (digits[i] < 9) { digits[i]++; return digits; } // the carry stops here digits[i] = 0; // 9 + 1 = 10: write 0, carry 1 } digits.insert(digits.begin(), 1); // every digit was 9 return digits; }
public int[] plusOne(int[] digits) { for (int i = digits.length - 1; i >= 0; i--) { if (digits[i] < 9) { digits[i]++; return digits; } // the carry stops here digits[i] = 0; // 9 + 1 = 10: write 0, carry 1 } int[] out = new int[digits.length + 1]; // every digit was 9: 1, then zeros out[0] = 1; return out; }
def plusOne(digits): for i in range(len(digits) - 1, -1, -1): if digits[i] < 9: # the carry stops here digits[i] += 1 return digits digits[i] = 0 # 9 + 1 = 10: write 0, carry 1 return [1] + digits # every digit was 9
Dropping the last carry. When every digit is 9 the loop ends with all zeros and a carry still owed. Returning the array then turns [9] into [0], not [1, 0].
The letters are the digits 1 to 26 of a base with no 0. Subtract 1, and the last letter is the remainder mod 26 counted from A. The quotient is the title before it, so repeat on it, and reverse the letters at the end.
convertToTitle(52)?
51 mod 26 = 25, which is Z, and 51 / 26 = 1. Then 0 mod 26 = 0, which is A. Reversed, AZ, and 1 × 26 + 26 = 52.
Why subtract 1 before taking n mod 26?
In ordinary base 26 the digits are 0 to 25. Here Z stands for 26, so shifting every letter down by 1 makes them ordinary digits for one step.
convertToTitle(703)?
702 mod 26 = 0 gives A and leaves 27. 26 mod 26 = 0 gives A and leaves 1. 0 gives A. ZZ is 702, so 703 is the first three-letter title.
Turn a column number into its Excel title: 1 is A, 26 is Z, 27 is AA.
Titles are numbers in base 26, but the digits run from A = 1 to Z = 26 and there is no zero. Subtract 1 first, and the last letter is (n − 1) mod 26 counted from A, a digit from 0 to 25. The rest of the title is the number (n − 1) / 26, so repeat on it until nothing is left. The letters come out last first, so reverse them.
string convertToTitle(int columnNumber) { string t; int n = columnNumber; while (n > 0) { n--; // the letters are 1 to 26, so shift to 0 to 25 t += char('A' + n % 26); // the last letter n /= 26; // the title before it } reverse(t.begin(), t.end()); return t; }
public String convertToTitle(int columnNumber) { StringBuilder t = new StringBuilder(); int n = columnNumber; while (n > 0) { n--; // the letters are 1 to 26, so shift to 0 to 25 t.append((char) ('A' + n % 26)); // the last letter n /= 26; // the title before it } return t.reverse().toString(); }
def convertToTitle(columnNumber): n, t = columnNumber, [] while n > 0: n -= 1 # the letters are 1 to 26, so shift to 0 to 25 t.append(chr(ord("A") + n % 26)) # the last letter n //= 26 # the title before it return "".join(reversed(t))
Shifting only the letter. Taking the letter from (n − 1) mod 26 but dividing n, not n − 1, by 26 leaves a stray carry. 26 comes out AZ; Z is right.
Long division makes each digit from the remainder alone, and a remainder is below the denominator. So within b digits a remainder comes back, and everything after it repeats. The map remembers where each remainder's digit went, which is where the bracket goes.
isHappy(20)?
20 goes 4, 16, 37, 58, 89, 145, 42 and back to 20. The cycle never holds 1.
Why must the walk of digit-square sums come back to a value?
A number with d digits maps to at most 81d. From 999 or below the next value is at most 243, so the walk is trapped among fewer than 1000 values and must repeat one.
Replace n by the sum of the squares of its digits again and again. Does it reach 1?
A number with d digits maps to at most 81d, so after a step or two every value is below 1000, and from there it stays below 1000. A walk on finitely many values must repeat one, and after that it goes round a cycle forever. So the question is whether the cycle is the one at 1. Run a slow walker one step at a time and a fast one two steps at a time. Inside the cycle the fast one gains a step each round, so they meet, and they meet at 1 when 1 is the cycle.
int sq(int n) { // the sum of the squares of the digits int s = 0; for (; n > 0; n /= 10) s += (n % 10) * (n % 10); return s; } bool isHappy(int n) { int slow = n, fast = sq(n); while (fast != 1 && slow != fast) { // a finite walk must repeat slow = sq(slow); fast = sq(sq(fast)); // gains one step a round } return fast == 1; }
int sq(int n) { // the sum of the squares of the digits int s = 0; for (; n > 0; n /= 10) s += (n % 10) * (n % 10); return s; } public boolean isHappy(int n) { int slow = n, fast = sq(n); while (fast != 1 && slow != fast) { // a finite walk must repeat slow = sq(slow); fast = sq(sq(fast)); // gains one step a round } return fast == 1; }
def sq(n): # the sum of the squares of the digits s = 0 while n > 0: s += (n % 10) ** 2 n //= 10 return s def isHappy(n): slow, fast = n, sq(n) while fast != 1 and slow != fast: # a finite walk must repeat slow = sq(slow) fast = sq(sq(fast)) # gains one step a round return fast == 1
Starting both walkers on n. Then slow equals fast before either moves, the loop never runs, and only n = 1 is happy. 7 goes 49, 97, 130, 10, 1, and comes out false.
Write numerator / denominator as a decimal, with the repeating part in brackets.
Long division makes one digit per step from a remainder r below the denominator: the digit is 10r / b and the next remainder is 10r mod b. Everything after depends only on r, so when a remainder comes back the digits since its first visit repeat forever. Keep a map from each remainder to where its digit went. A remainder of 0 ends the decimal, and one seen before puts the bracket at its first place. Work with absolute values in 64 bits, and put the sign in first.
string fractionToDecimal(int numerator, int denominator) { long long a = numerator, b = denominator; // −2^31 / −1 does not fit an int string s; if (a != 0 && (a < 0) != (b < 0)) s += '-'; a = llabs(a); b = llabs(b); s += to_string(a / b); long long r = a % b; if (r == 0) return s; s += '.'; unordered_map<long long, int> at; // remainder -> where its digit went while (r != 0 && !at.count(r)) { at[r] = s.size(); r *= 10; s += char('0' + r / b); r %= b; } if (r != 0) { s.insert(at[r], "("); s += ')'; } // the remainder came back return s; }
public String fractionToDecimal(int numerator, int denominator) { long a = numerator, b = denominator; // −2^31 / −1 does not fit an int StringBuilder s = new StringBuilder(); if (a != 0 && (a < 0) != (b < 0)) s.append('-'); a = Math.abs(a); b = Math.abs(b); s.append(a / b); long r = a % b; if (r == 0) return s.toString(); s.append('.'); Map<Long, Integer> at = new HashMap<>(); // remainder -> where its digit went while (r != 0 && !at.containsKey(r)) { at.put(r, s.length()); r *= 10; s.append(r / b); r %= b; } if (r != 0) { s.insert((int) at.get(r), "("); s.append(')'); } // the remainder came back return s.toString(); }
def fractionToDecimal(numerator, denominator): sign = "-" if numerator * denominator < 0 else "" a, b = abs(numerator), abs(denominator) s = sign + str(a // b) r = a % b if r == 0: return s s += "." at = {} # remainder -> where its digit went while r and r not in at: at[r] = len(s) r *= 10 s += str(r // b) r %= b if r: # the remainder came back s = s[:at[r]] + "(" + s[at[r]:] + ")" return s
A minus sign on zero. Testing only whether the signs differ writes 0 / −5 as −0. The answer is 0, so the sign also needs a numerator that is not 0.
fractionToDecimal(1, 6)?
r = 1 gives the digit 1 and r = 4. r = 4 gives 6 and r = 4 again, so only the 6 repeats, from its first place.
Why is the map keyed by the remainder and not by the digit?
Two places can make the same digit from different remainders, as 1 / 6 makes 1 then 6, while 1 / 7 makes 1 and 4 before any repeat. Only a repeated remainder repeats what follows.
Two points lie on one line through p exactly when their directions from p are parallel. Dividing a direction by the gcd of its parts and making the first non-zero part positive gives one exact pair of integers per line, so a map can count them.
The key for the direction from (1, 4) to (−2, −2)?
dx = −3 and dy = −6, with gcd 3, so (−1, −2). dx is negative, so both signs flip.
Why reduce by the gcd instead of keying the map by dy / dx?
Floating-point division rounds, so equal slopes can come out as different doubles, and a vertical line divides by 0. A reduced pair of integers is exact.
Given up to 300 points, find the most that lie on one straight line.
Fix a point p. Every other point q lies on the line through p in the direction q − p, and two points share a line through p when their directions are parallel. Divide (dx, dy) by gcd(|dx|, |dy|) and make the first non-zero part positive, and parallel directions become the same pair of integers, with no division and no rounding. Count the pairs for each p. The best count plus p itself is the answer.
int maxPoints(vector<vector<int>>& points) { int n = points.size(), best = 1; for (int i = 0; i < n; i++) { map<pair<int, int>, int> cnt; // direction from p -> points along it for (int j = i + 1; j < n; j++) { int dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1]; int g = __gcd(abs(dx), abs(dy)); // points are distinct, so g > 0 dx /= g; dy /= g; if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; } // one sign per line best = max(best, ++cnt[{dx, dy}] + 1); } } return best; }
public int maxPoints(int[][] points) { int n = points.length, best = 1; for (int i = 0; i < n; i++) { Map<Long, Integer> cnt = new HashMap<>(); // direction from p -> points along it for (int j = i + 1; j < n; j++) { int dx = points[j][0] - points[i][0], dy = points[j][1] - points[i][1]; int g = gcd(Math.abs(dx), Math.abs(dy)); // points are distinct, so g > 0 dx /= g; dy /= g; if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; } // one sign per line long key = dx * 100000L + dy; int c = cnt.merge(key, 1, Integer::sum); best = Math.max(best, c + 1); } } return best; } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
from math import gcd def maxPoints(points): n, best = len(points), 1 for i in range(n): cnt = {} # direction from p -> points along it for j in range(i + 1, n): dx = points[j][0] - points[i][0] dy = points[j][1] - points[i][1] g = gcd(dx, dy) # points are distinct, so g > 0 dx, dy = dx // g, dy // g if dx < 0 or (dx == 0 and dy < 0): # one sign per line dx, dy = -dx, -dy cnt[(dx, dy)] = cnt.get((dx, dy), 0) + 1 best = max(best, cnt[(dx, dy)] + 1) return best
Two signs for one line. (1, 1) and (−1, −1) are the same direction. Without fixing the sign, [[0, 0], [1, 1], [−1, −1]] counts 2 from every point, though all 3 are on one line.
Two numbers have a gcd of at least d when d divides both. So walk d down from the largest value, count the numbers sitting at d, 2d, 3d, and stop at the first d that finds two. The walks over all d cost M log M.
Common Divisors on 6 10 15?
gcd(6, 10) = 2, gcd(6, 15) = 3 and gcd(10, 15) = 5. Walking d down from 15, d = 5 is the first to find two numbers, 10 and 15.
Why is the walk over every d only O(M log M)?
M / 1 + M / 2 + M / 3 + … is M times the harmonic sum, which grows like ln M.
Among up to 2 · 10⁵ numbers no larger than 10⁶, find the largest gcd of any two.
Trying every pair is 2 · 10¹⁰ gcds. Turn it round. Two of the numbers have a gcd of at least d exactly when d divides both of them, so the answer is the largest d that divides two of the numbers. Count how often each value occurs. For each d from the top down, add up the counts at d, 2d, 3d and so on, and stop at the first d whose total reaches 2. The sums over all d cost M / 1 + M / 2 + … = O(M log M).
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<int> x(n); for (int& v : x) scanf("%d", &v); int M = *max_element(x.begin(), x.end()); vector<int> cnt(M + 1, 0); for (int v : x) cnt[v]++; for (int d = M; d >= 1; d--) { // the largest d first int k = 0; for (int m = d; m <= M && k < 2; m += d) k += cnt[m]; // the numbers d divides if (k >= 2) { printf("%d\n", d); return 0; } } }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringTokenizer st = new StringTokenizer(in.readLine()); int[] x = new int[n]; int M = 0; for (int i = 0; i < n; i++) { x[i] = Integer.parseInt(st.nextToken()); M = Math.max(M, x[i]); } int[] cnt = new int[M + 1]; for (int v : x) cnt[v]++; for (int d = M; d >= 1; d--) { // the largest d first int k = 0; for (int m = d; m <= M && k < 2; m += d) k += cnt[m]; // the numbers d divides if (k >= 2) { System.out.println(d); return; } } } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) x = list(map(int, data[1:1 + n])) M = max(x) cnt = [0] * (M + 1) for v in x: cnt[v] += 1 for d in range(M, 0, -1): # the largest d first k = 0 for m in range(d, M + 1, d): # the numbers d divides k += cnt[m] if k >= 2: print(d) return main()
Marking values instead of counting them. With a seen flag in place of a count, two equal numbers look like one. [2, 2] has gcd 2, but each d then finds a single value and the search finds nothing.
A number left standing when the walk reaches it has no smaller prime factor, so it is prime. Its multiples below its square have a smaller factor and are crossed out already, so each prime starts at its square, and the sieve stops once the square passes the end.
Which of 4, 9, 25, 36 is not a T-prime?
4, 9 and 25 are squares of the primes 2, 3 and 5. 36 is 6², and 6 is not prime, so 36 has nine divisors.
Why may each prime start crossing out at p × p?
A multiple k × p with k < p has a prime factor of k, smaller than p, whose turn came earlier and crossed it out.
For up to 10⁵ numbers as large as 10¹², say whether each has exactly three divisors.
Divisors come in pairs d and x / d, so an odd count means x is a perfect square, with its root r paired with itself. Three divisors are then 1, r and x, and nothing else divides x exactly when nothing else divides r, so r is prime. x ≤ 10¹² makes r ≤ 10⁶. A sieve of Eratosthenes to 10⁶ crosses out the multiples of each prime from its square and leaves the primes, and each query takes an exact integer square root and one look.
#include <bits/stdc++.h> using namespace std; long long isqrt(long long x) { // the exact floor of √x long long r = (long long)sqrt((double)x); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> x(n); for (auto& v : x) cin >> v; int M = isqrt(*max_element(x.begin(), x.end())); vector<bool> prime(M + 1, true); prime[0] = prime[1] = false; for (long long p = 2; p * p <= M; p++) if (prime[p]) for (long long q = p * p; q <= M; q += p) prime[q] = false; // cross out p's multiples string out; for (long long v : x) { long long r = isqrt(v); out += r * r == v && prime[r] ? "YES\n" : "NO\n"; // 1, r and r² only } cout << out; }
import java.io.*; import java.util.*; public class Main { static long isqrt(long x) { // the exact floor of √x long r = (long) Math.sqrt((double) x); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringTokenizer st = new StringTokenizer(in.readLine()); long[] x = new long[n]; long big = 1; for (int i = 0; i < n; i++) { x[i] = Long.parseLong(st.nextToken()); big = Math.max(big, x[i]); } int M = (int) isqrt(big); boolean[] prime = new boolean[M + 1]; Arrays.fill(prime, true); prime[0] = prime[1] = false; for (long p = 2; p * p <= M; p++) if (prime[(int) p]) for (long q = p * p; q <= M; q += p) prime[(int) q] = false; // cross out p's multiples StringBuilder out = new StringBuilder(); for (long v : x) { long r = isqrt(v); out.append(r * r == v && prime[(int) r] ? "YES\n" : "NO\n"); // 1, r and r² only } System.out.print(out); } }
import sys from math import isqrt def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) x = list(map(int, data[1:1 + n])) M = isqrt(max(x)) prime = bytearray([1]) * (M + 1) prime[0] = prime[1] = 0 for p in range(2, isqrt(M) + 1): if prime[p]: # cross out p's multiples prime[p * p::p] = bytearray(len(range(p * p, M + 1, p))) out = [] for v in x: r = isqrt(v) out.append("YES" if r * r == v and prime[r] else "NO") # 1, r and r² only print("\n".join(out)) main()
Any perfect square. A square has an odd number of divisors, but only the square of a prime has three. 16 = 4² has five, 1, 2, 4, 8 and 16.
Among the primes between left and right, find the two closest, the smaller pair on a tie.
Sieve once up to right, then walk the numbers from left in order and keep the last prime seen. Each new prime makes a pair with it, and only neighbouring primes can be the closest pair, since a prime between two others is closer to both. Keep the pair with the smallest gap; a strict < keeps the earlier pair on a tie.
vector<int> closestPrimes(int left, int right) { vector<bool> prime(right + 1, true); prime[0] = prime[1] = false; for (long long p = 2; p * p <= right; p++) if (prime[p]) for (long long q = p * p; q <= right; q += p) prime[q] = false; vector<int> best = {-1, -1}; int prev = -1; // the last prime met for (int x = left; x <= right; x++) { if (!prime[x]) continue; if (prev != -1 && (best[0] == -1 || x - prev < best[1] - best[0])) best = {prev, x}; // < keeps the earlier pair on a tie prev = x; } return best; }
public int[] closestPrimes(int left, int right) { boolean[] prime = new boolean[right + 1]; Arrays.fill(prime, true); prime[0] = prime[1] = false; for (long p = 2; p * p <= right; p++) if (prime[(int) p]) for (long q = p * p; q <= right; q += p) prime[(int) q] = false; int[] best = {-1, -1}; int prev = -1; // the last prime met for (int x = left; x <= right; x++) { if (!prime[x]) continue; if (prev != -1 && (best[0] == -1 || x - prev < best[1] - best[0])) best = new int[]{prev, x}; // < keeps the earlier pair on a tie prev = x; } return best; }
def closestPrimes(left, right): prime = bytearray([1]) * (right + 1) prime[0] = prime[1] = 0 p = 2 while p * p <= right: if prime[p]: prime[p * p::p] = bytearray(len(range(p * p, right + 1, p))) p += 1 best, prev = [-1, -1], -1 # prev: the last prime met for x in range(left, right + 1): if not prime[x]: continue if prev != -1 and (best[0] == -1 or x - prev < best[1] - best[0]): best = [prev, x] # < keeps the earlier pair on a tie prev = x return best
Leaving 1 marked prime. The sieve crosses out multiples, and 1 is a multiple of nothing, so it must be cleared by hand. Otherwise left = 1, right = 2 returns [1, 2], not [−1, −1].
closestPrimes(1, 10)?
The primes are 2, 3, 5 and 7. 2 and 3 differ by 1, the only gap smaller than 2.
A sieve that writes into each number the first prime that reaches it stores its smallest prime factor. Factoring is then looking up, dividing out every copy, and looking up again on what is left. Each prime p with exponent e multiplies the count of divisors by e + 1.
Counting Divisors on 12?
12 = 2² × 3, so (2 + 1)(1 + 1) = 6: 1, 2, 3, 4, 6 and 12.
Why must the spf sieve run p up to M and not stop at √M?
Stopping at √M still labels every composite, but a prime p above √M is reached only when the outer loop gets to p, which writes spf[p] = p.
How many divisors does 360 = 2³ × 3² × 5 have?
(3 + 1)(2 + 1)(1 + 1) = 24. A divisor picks 0 to 3 twos, 0 to 2 threes and 0 or 1 five.
For up to 10⁵ numbers no larger than 10⁶, print how many divisors each has.
If x = p₁^e₁ · p₂^e₂ ⋯, a divisor picks 0 to e₁ copies of p₁, 0 to e₂ of p₂, and so on, so there are (e₁ + 1)(e₂ + 1)⋯ of them. Factoring by trial division costs √x per number. A sieve that stores spf[x], the smallest prime factor of every x, factors any x in O(log x): divide out spf[x], then spf of what is left, until 1. The sieve walks every prime p to the end and gives spf = p to each multiple still unlabelled.
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<int> xs(n); for (int& v : xs) scanf("%d", &v); int M = *max_element(xs.begin(), xs.end()); vector<int> spf(M + 1, 0); // spf[x]: the smallest prime factor of x for (int p = 2; p <= M; p++) if (spf[p] == 0) // nothing smaller divides p, so p is prime for (int q = p; q <= M; q += p) if (spf[q] == 0) spf[q] = p; for (int x : xs) { int d = 1; while (x > 1) { int p = spf[x], e = 0; while (x % p == 0) { x /= p; e++; } // p^e divides x exactly d *= e + 1; // 0 to e copies of p } printf("%d\n", d); } }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); int[] xs = new int[n]; int M = 1; for (int i = 0; i < n; i++) { xs[i] = Integer.parseInt(in.readLine().trim()); M = Math.max(M, xs[i]); } int[] spf = new int[M + 1]; // spf[x]: the smallest prime factor of x for (int p = 2; p <= M; p++) if (spf[p] == 0) // nothing smaller divides p, so p is prime for (int q = p; q <= M; q += p) if (spf[q] == 0) spf[q] = p; StringBuilder out = new StringBuilder(); for (int x : xs) { int d = 1; while (x > 1) { int p = spf[x], e = 0; while (x % p == 0) { x /= p; e++; } // p^e divides x exactly d *= e + 1; // 0 to e copies of p } out.append(d).append('\n'); } System.out.print(out); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) xs = list(map(int, data[1:1 + n])) M = max(xs) spf = [0] * (M + 1) # spf[x]: the smallest prime factor of x for p in range(2, M + 1): if spf[p] == 0: # nothing smaller divides p, so p is prime for q in range(p, M + 1, p): if spf[q] == 0: spf[q] = p out = [] for x in xs: d = 1 while x > 1: p, e = spf[x], 0 while x % p == 0: # p^e divides x exactly x //= p e += 1 d *= e + 1 # 0 to e copies of p out.append(d) print("\n".join(map(str, out))) main()
Sieving only to √M. That is enough to cross out every composite, but an spf table must also label the primes. With p only up to 1000, a prime x above 1000, such as 1009, keeps spf[x] = 0 and never divides out.
The sum of σ(i) is the sum of d × (n / d). The quotient n / d stays the same over a whole block of d, from l to n / (n / l), and takes fewer than 2√n values. One step per block adds the quotient times the sum of the block.
For n = 12, which d have n / d = 2?
l = 5 gives q = 12 / 5 = 2 and r = 12 / 2 = 6. 12 / 4 is 3 and 12 / 7 is 1.
Why are there fewer than 2√n blocks?
Fewer than √n blocks start at a d up to √n. Past √n the quotient itself is below √n, so it has fewer than √n values left to take.
Sum of Divisors for n = 3?
σ(1) + σ(2) + σ(3) = 1 + 3 + 4 = 8. As blocks, 1 × 3 + (2 + 3) × 1 = 8.
Find σ(1) + σ(2) + … + σ(n) mod 10⁹ + 7, where σ(i) is the sum of the divisors of i, for n up to 10¹².
Swap the order of the sum. A number d is a divisor of d, 2d, 3d, …, so of n / d numbers up to n, and the total is the sum of d · (n / d) over d from 1 to n. That is still 10¹² terms, but n / d takes fewer than 2√n different values. For d from l, every d up to r = n / (n / l) gives the same q = n / l, so the whole block adds q · (l + … + r). The block sum is (l + r)(r − l + 1) / 2, and one of the two factors is even, so halve that one before taking anything mod P.
#include <bits/stdc++.h> using namespace std; int main() { const long long P = 1000000007; long long n; scanf("%lld", &n); long long total = 0; for (long long l = 1; l <= n; ) { long long q = n / l, r = n / q; // every d in [l, r] has n / d = q long long a = l + r, b = r - l + 1; // l + ... + r = a * b / 2 if (a % 2 == 0) a /= 2; else b /= 2; // halve the even one before any mod long long s = (a % P) * (b % P) % P; total = (total + q % P * s) % P; // each d divides q numbers up to n l = r + 1; } printf("%lld\n", total); }
import java.io.*; public class Main { public static void main(String[] args) throws IOException { final long P = 1000000007L; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); long n = Long.parseLong(in.readLine().trim()); long total = 0; for (long l = 1; l <= n; ) { long q = n / l, r = n / q; // every d in [l, r] has n / d = q long a = l + r, b = r - l + 1; // l + ... + r = a * b / 2 if (a % 2 == 0) a /= 2; else b /= 2; // halve the even one before any mod long s = (a % P) * (b % P) % P; total = (total + q % P * s) % P; // each d divides q numbers up to n l = r + 1; } System.out.println(total); } }
import sys def main(): P = 1000000007 n = int(sys.stdin.readline()) total, l = 0, 1 while l <= n: q = n // l r = n // q # every d in [l, r] has n // d = q a, b = l + r, r - l + 1 # l + ... + r = a * b / 2 if a % 2 == 0: # halve the even one before any mod a //= 2 else: b //= 2 s = (a % P) * (b % P) % P total = (total + q % P * s) % P # each d divides q numbers up to n l = r + 1 print(total) main()
Halving after the mod. (a mod P)(b mod P) / 2 is not ab / 2 mod P once a or b reaches P, since the reduced product can be odd. n = 10⁹ still passes and n = 10¹² fails. Halve the even factor first, while it is exact.
A trailing zero needs a 2 and a 5, and the 5s are scarcer. The multiples of 5 each give one, the multiples of 25 a second, of 125 a third. Dividing n by 5 again and again counts exactly those, one round per power of 5.
trailingZeroes(30)?
30 / 5 = 6 multiples of 5, and 30 / 25 = 1 of them, 25, has a second 5. 6 + 1 = 7.
Why count the 5s in n! and not the 2s?
Every second number gives a 2 and only every fifth a 5, so the 5s run out first and decide how many 10s there are.
Count the trailing zeroes of n!.
Each trailing zero is a factor 10 = 2 · 5, and n! has more 2s than 5s, so count the 5s. Every multiple of 5 up to n gives one, and there are n / 5 of them. Multiples of 25 give a second, n / 25 more, multiples of 125 a third, and so on. Dividing n by 5 again and again produces exactly n / 5, n / 25, n / 125, … to add up.
int trailingZeroes(int n) { int z = 0; while (n > 0) { n /= 5; // the multiples of 5, then 25, then 125, ... z += n; } return z; }
public int trailingZeroes(int n) { int z = 0; while (n > 0) { n /= 5; // the multiples of 5, then 25, then 125, ... z += n; } return z; }
def trailingZeroes(n): z = 0 while n > 0: n //= 5 # the multiples of 5, then 25, then 125, ... z += n return z
Counting each multiple of 5 once. 25 = 5 · 5 brings two 5s. n / 5 alone gives 25! five zeroes; it has six.
a^b is the product of a^(2^k) over the bits k set in b. Walk the bits from the lowest. Each round multiplies r by the current power when the bit is set, then squares the power. b of 10⁹ takes 30 rounds, not 10⁹ products.
power(3, 13, 1000)?
13 = 1101₂, so 3¹³ = 3⁸ × 3⁴ × 3 = 1594323, and mod 1000 that is 323.
How many squarings does power make for b = 10⁹?
10⁹ is below 2³⁰, so it has 30 bits, and each bit costs one squaring and at most one multiplication.
Why reduce a mod m before the loop and after every product?
Two factors below 10⁹ + 7 multiply to below 1.1 × 10¹⁸, which fits a 64-bit integer. Unreduced, a² would overflow after one round.
Compute 2 · 10⁵ values a^b mod 10⁹ + 7, with a and b up to 10⁹.
Multiplying b times is 10⁹ steps per query. Write b in binary instead. a^b is the product of a^(2^k) over the bits k set in b, and each a^(2^k) is the square of the one before. So walk the bits of b from the lowest: when a bit is set, multiply the result by the current power, then square the power and shift b. Every product is taken mod P, and with both factors below P it fits in 64 bits.
#include <bits/stdc++.h> using namespace std; long long power(long long a, long long b, long long m) { // a^b mod m long long r = 1 % m; a %= m; while (b > 0) { if (b & 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } int main() { const long long P = 1000000007; int n; scanf("%d", &n); while (n--) { long long a, b; scanf("%lld %lld", &a, &b); printf("%lld\n", power(a, b, P)); } }
import java.io.*; import java.util.*; public class Main { static long power(long a, long b, long m) { // a^b mod m long r = 1 % m; a %= m; while (b > 0) { if ((b & 1) == 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } public static void main(String[] args) throws IOException { final long P = 1000000007L; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); while (n-- > 0) { StringTokenizer st = new StringTokenizer(in.readLine()); long a = Long.parseLong(st.nextToken()), b = Long.parseLong(st.nextToken()); out.append(power(a, b, P)).append('\n'); } System.out.print(out); } }
import sys def power(a, b, m): # a^b mod m r, a = 1 % m, a % m while b > 0: if b & 1: # this bit of b is set r = r * a % m a = a * a % m # a, a^2, a^4, a^8, ... b >>= 1 return r def main(): P = 1000000007 data = sys.stdin.buffer.read().split() n = int(data[0]) out = [] for t in range(n): a, b = int(data[1 + 2 * t]), int(data[2 + 2 * t]) out.append(power(a, b, P)) print("\n".join(map(str, out))) main()
Taking 0⁰ as 0. A shortcut that returns 0 whenever a is 0 breaks the statement's rule that 0⁰ = 1. With r starting at 1 and no shortcut, b = 0 returns 1 for every a.
For a prime P, a^(P − 1) = 1 whenever P does not divide a. So the powers of a repeat every P − 1 exponents, and a huge exponent can be cut mod P − 1 before the last power. The bench's P is 13, so the powers of 2 repeat every 12.
2^100 mod 13?
100 mod 12 = 4, so 2¹⁰⁰ = 2⁴ = 16, and 16 mod 13 = 3.
Why is the exponent cut mod P − 1 and not mod P?
Fermat's little theorem. The powers of a come back to 1 after P − 1 steps, so exponents that differ by a multiple of P − 1 give the same value.
Compute a^(b^c) mod 10⁹ + 7, where b^c can have billions of digits.
P = 10⁹ + 7 is prime, so Fermat's little theorem gives a^(P − 1) ≡ 1 for any a that P does not divide. Powers of a then repeat every P − 1 steps, and the exponent b^c can be cut to b^c mod (P − 1), which square and multiply computes without ever writing b^c down. The cut is mod P − 1, not mod P. The only a that P divides here is 0, and b^c mod (P − 1) is 0 only when b is 0, so 0⁰ = 1 still comes out right.
#include <bits/stdc++.h> using namespace std; long long power(long long a, long long b, long long m) { // a^b mod m long long r = 1 % m; a %= m; while (b > 0) { if (b & 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } int main() { const long long P = 1000000007; int n; scanf("%d", &n); while (n--) { long long a, b, c; scanf("%lld %lld %lld", &a, &b, &c); long long e = power(b, c, P - 1); // a^(P − 1) = 1, so cut the exponent mod P − 1 printf("%lld\n", power(a, e, P)); } }
import java.io.*; import java.util.*; public class Main { static long power(long a, long b, long m) { // a^b mod m long r = 1 % m; a %= m; while (b > 0) { if ((b & 1) == 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } public static void main(String[] args) throws IOException { final long P = 1000000007L; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); while (n-- > 0) { StringTokenizer st = new StringTokenizer(in.readLine()); long a = Long.parseLong(st.nextToken()), b = Long.parseLong(st.nextToken()), c = Long.parseLong(st.nextToken()); long e = power(b, c, P - 1); // a^(P − 1) = 1, so cut the exponent mod P − 1 out.append(power(a, e, P)).append('\n'); } System.out.print(out); } }
import sys def power(a, b, m): # a^b mod m r, a = 1 % m, a % m while b > 0: if b & 1: # this bit of b is set r = r * a % m a = a * a % m # a, a^2, a^4, a^8, ... b >>= 1 return r def main(): P = 1000000007 data = sys.stdin.buffer.read().split() n = int(data[0]) out = [] for t in range(n): a, b, c = (int(v) for v in data[1 + 3 * t:4 + 3 * t]) e = power(b, c, P - 1) # a^(P − 1) = 1, so cut the exponent mod P − 1 out.append(power(a, e, P)) print("\n".join(map(str, out))) main()
Cutting the exponent mod P. Powers of a repeat every P − 1 steps, not every P. The samples' exponents are all below P, so the wrong cut passes them. It fails on a = 2, b = 2, c = 30, where b^c = 2³⁰ is past P.
A division mod a prime is a multiplication by the inverse, and Fermat gives it as x^(P − 2). Take one inverse, of the largest factorial, by a fast power. 1 / (i − 1)! = i / i! gives every smaller one by one multiplication.
C(5, 2) mod 7 from f = 1 1 2 6 3 1, inv[2] = 4, inv[3] = 6?
f[5] × inv[2] × inv[3] = 1 × 4 × 6 = 24, and 24 mod 7 = 3. C(5, 2) = 10, and 10 mod 7 = 3 too.
Why take one inverse by a power and the rest by inv[i − 1] = inv[i] × i?
A fast power is about 30 squarings. The walk down costs one multiplication per entry, so a table of 10⁶ inverses takes 10⁶ steps, not 3 · 10⁷.
Answer 10⁵ queries C(a, b) mod 10⁹ + 7 with a up to 10⁶.
C(a, b) = a! / (b! (a − b)!), but a division mod P is a multiplication by an inverse. By Fermat, x^(P − 2) is the inverse of x mod P. Store every factorial up to the largest a, then one inverse, of the largest factorial, by a fast power. The rest come down the table for free, since 1 / (i − 1)! = i / i!. Each query is then two multiplications.
#include <bits/stdc++.h> using namespace std; long long power(long long a, long long b, long long m) { // a^b mod m long long r = 1 % m; a %= m; while (b > 0) { if (b & 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } int main() { const long long P = 1000000007; int n; scanf("%d", &n); vector<int> a(n), b(n); for (int i = 0; i < n; i++) scanf("%d %d", &a[i], &b[i]); int M = *max_element(a.begin(), a.end()); vector<long long> f(M + 1), inv(M + 1); f[0] = 1; for (int i = 1; i <= M; i++) f[i] = f[i - 1] * i % P; inv[M] = power(f[M], P - 2, P); // Fermat: x^(P − 2) is 1 / x for (int i = M; i > 0; i--) inv[i - 1] = inv[i] * i % P; // 1 / (i − 1)! = i / i! for (int i = 0; i < n; i++) printf("%lld\n", f[a[i]] * inv[b[i]] % P * inv[a[i] - b[i]] % P); }
import java.io.*; import java.util.*; public class Main { static long power(long a, long b, long m) { // a^b mod m long r = 1 % m; a %= m; while (b > 0) { if ((b & 1) == 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } public static void main(String[] args) throws IOException { final long P = 1000000007L; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); int[] a = new int[n], b = new int[n]; int M = 0; for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); a[i] = Integer.parseInt(st.nextToken()); b[i] = Integer.parseInt(st.nextToken()); M = Math.max(M, a[i]); } long[] f = new long[M + 1], inv = new long[M + 1]; f[0] = 1; for (int i = 1; i <= M; i++) f[i] = f[i - 1] * i % P; inv[M] = power(f[M], P - 2, P); // Fermat: x^(P − 2) is 1 / x for (int i = M; i > 0; i--) inv[i - 1] = inv[i] * i % P; // 1 / (i − 1)! = i / i! StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) out.append(f[a[i]] * inv[b[i]] % P * inv[a[i] - b[i]] % P).append('\n'); System.out.print(out); } }
import sys def power(a, b, m): # a^b mod m r, a = 1 % m, a % m while b > 0: if b & 1: # this bit of b is set r = r * a % m a = a * a % m # a, a^2, a^4, a^8, ... b >>= 1 return r def main(): P = 1000000007 data = sys.stdin.buffer.read().split() n = int(data[0]) q = [(int(data[1 + 2 * t]), int(data[2 + 2 * t])) for t in range(n)] M = max(a for a, b in q) f = [1] * (M + 1) for i in range(1, M + 1): f[i] = f[i - 1] * i % P inv = [1] * (M + 1) inv[M] = power(f[M], P - 2, P) # Fermat: x^(P − 2) is 1 / x for i in range(M, 0, -1): inv[i - 1] = inv[i] * i % P # 1 / (i − 1)! = i / i! out = [f[a] * inv[b] % P * inv[a - b] % P for a, b in q] print("\n".join(map(str, out))) main()
Dividing the reduced factorials. f[a] / (f[b] · f[a − b]) as an integer division is right only while a! is below P. It passes all three samples, and 13! is the first factorial past P, so C(13, 1) already comes out 0.
Count the numbers of length n, made of the digits a and b only, whose digit sum is also made of a and b only, mod 10⁹ + 7.
There are 2ⁿ numbers to test, but the digit sum depends only on how many digits are a. With i of them it is a·i + b·(n − i), and the C(n, i) ways to place the a digits all share it. So loop i from 0 to n, test that one sum digit by digit, and add C(n, i) when it passes. The factorial tables of row 14 give each C(n, i) in O(1).
#include <bits/stdc++.h> using namespace std; long long power(long long a, long long b, long long m) { // a^b mod m long long r = 1 % m; a %= m; while (b > 0) { if (b & 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } int main() { const long long P = 1000000007; int a, b, n; scanf("%d %d %d", &a, &b, &n); vector<long long> f(n + 1), inv(n + 1); f[0] = 1; for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % P; inv[n] = power(f[n], P - 2, P); for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % P; long long total = 0; for (int i = 0; i <= n; i++) { // i digits are a, n − i are b int s = a * i + b * (n - i); // the sum depends only on i bool good = true; for (; s > 0; s /= 10) // every digit of the sum if (s % 10 != a && s % 10 != b) good = false; if (good) total = (total + f[n] * inv[i] % P * inv[n - i]) % P; // C(n, i) placings } printf("%lld\n", total); }
import java.io.*; import java.util.*; public class Main { static long power(long a, long b, long m) { // a^b mod m long r = 1 % m; a %= m; while (b > 0) { if ((b & 1) == 1) r = r * a % m; // this bit of b is set a = a * a % m; // a, a^2, a^4, a^8, ... b >>= 1; } return r; } public static void main(String[] args) throws IOException { final long P = 1000000007L; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken()), n = Integer.parseInt(st.nextToken()); long[] f = new long[n + 1], inv = new long[n + 1]; f[0] = 1; for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % P; inv[n] = power(f[n], P - 2, P); for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % P; long total = 0; for (int i = 0; i <= n; i++) { // i digits are a, n − i are b int s = a * i + b * (n - i); // the sum depends only on i boolean good = true; for (; s > 0; s /= 10) // every digit of the sum if (s % 10 != a && s % 10 != b) good = false; if (good) total = (total + f[n] * inv[i] % P * inv[n - i]) % P; // C(n, i) placings } System.out.println(total); } }
import sys def power(a, b, m): # a^b mod m r, a = 1 % m, a % m while b > 0: if b & 1: # this bit of b is set r = r * a % m a = a * a % m # a, a^2, a^4, a^8, ... b >>= 1 return r def main(): P = 1000000007 a, b, n = map(int, sys.stdin.readline().split()) f = [1] * (n + 1) for i in range(1, n + 1): f[i] = f[i - 1] * i % P inv = [1] * (n + 1) inv[n] = power(f[n], P - 2, P) for i in range(n, 0, -1): inv[i - 1] = inv[i] * i % P total = 0 for i in range(n + 1): # i digits are a, n - i are b s = a * i + b * (n - i) # the sum depends only on i good = True while s > 0: # every digit of the sum if s % 10 != a and s % 10 != b: good = False s //= 10 if good: # C(n, i) placings total = (total + f[n] * inv[i] % P * inv[n - i]) % P print(total) main()
Testing one digit of the sum. An if where the while belongs checks only the last digit. Both samples pass, but with a = 2, b = 6 and n = 2, the sum 6 + 6 = 12 ends in a good digit and holds a 1, so 66 is counted and the answer 0 comes out 1.
Beautiful Numbers with a = 1, b = 2, n = 2?
11 has sum 2, a good number. 12 and 21 have sum 3 and 22 has sum 4, which are not. Only i = 2 passes, and C(2, 2) = 1.
Twelve moves, and each has a phrase in the statement that gives it away.
add from the right; stop at the first digit below 9
CARRYO(n)subtract 1, then take the remainder and divide
BIJECTIVE BASEO(log n)the values are finitely many, so watch for one coming back
FINITE MAPO(cycle)divide (dx, dy) by their gcd and fix the sign
REDUCED DIRECTIONO(n² log C)for each d, count the numbers at its multiples
MULTIPLESO(M log M)cross out each prime's multiples from its square
SIEVEO(M log log M)a table of smallest prime factors, then divide down
SPF TABLEO(log x) eachgroup the d whose quotient is the same
QUOTIENT BLOCKSO(√n)add n / p, n / p², n / p³, …
LEGENDREO(log n)square and multiply over the bits of b
FAST POWERO(log b)cut the exponent mod P − 1, by Fermat
FERMATO(log b)factorials, one inverse by a power, then walk down
INVERSE FACTORIALSO(M + q)Pow(x, n) for n up to 2³¹ − 1, without recursion. Which move?
Walk the bits of n, squaring x each round and multiplying it in when the bit is set. recursion-1 halves n with a call instead; the work is the same 31 rounds.
Count Primes asks how many primes lie below n, for n up to 5 · 10⁶. Which move?
Sieve up to n and count what is left standing. bit-manipulation runs the same sieve; testing each number by trial division would be n√n.
Count Good Numbers needs 5^a × 4^b mod 10⁹ + 7 for a and b up to 10¹⁵. Which move?
Two fast powers of about 50 rounds each. Fermat could cut the exponents mod P − 1 first, but at 10¹⁵ the bits are few enough without it.
Why does C(n, k) mod P need P to be prime?
With P prime, every x from 1 to P − 1 has an inverse, and Fermat gives it as x^(P − 2). Mod 10, 2 has none, so dividing by 2! would be impossible.
None of these fail the samples. Each one fails a hidden test.
Fermat makes the powers of a repeat every P − 1 steps. An exponent cut mod P passes every sample below P and fails beyond it.
f[a] / (f[b] · f[a − b]) on numbers already taken mod P is no longer a division of the factorials. Multiply by inverses.
A sieve crosses out multiples, and 1 is a multiple of nothing. Clear 0 and 1 by hand.
A square has an odd number of divisors, but only a prime's square has three. Check the root against the sieve.
(a mod P)(b mod P) can be odd when ab is even. Halve the even factor while it is still exact.
Signs that differ make a negative answer, unless the numerator is 0. 0 / −5 is 0.
Twelve moves on one page. The right column is the cue for each.
The carry stopped at the first digit below 9; a base with no 0 shifted before it divided; a remainder that came back repeated the digits; the gcd gave each line one direction; a divisor counted the numbers at its multiples; the sieve crossed out from each prime's square, and its smallest prime factors factored a number by looking up; the quotient n / d came in blocks; the fives in n! came one round per power of 5; square and multiply walked the bits; Fermat cut the exponent mod P − 1; and one inverse walked down the factorial table. Pow(x, n) is in recursion-1 and Count Primes in bit-manipulation.
Module 28. Fifteen problems: seven on LeetCode, six on CSES and two on Codeforces. Next in the sheet: advanced strings.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.