Freaks City

Miller-Rabin Primality TestThe Miller-Rabin algorithm is a probabilistic method used to determine if a large number is prime. It builds upon Fermat's Little Theorem, which states that for a prime $ p $ and integer $ a $ such that $ 1 \le a < p $, the congruence $ a^{p-1} \equiv 1 \pmod p $ holds. However, relying solely on this theorem allows f ...

Dirichlet Convolution Dirichlet convolution is a binary operation defined between arithmetic functions. It can be expressed as \((f * g)(n) = \sum_{xy = n} f(x) \cdot g(y)\) or equivalently \((f * g)(n) = \sum_{d \mid n} f(d) \cdot g(\frac{n}{d})\). Properties If both \(f\) and \(g\) are multiplicative functions, then \(f * g\) is also multipl ...

Holiday Reading A book has n pages. A student can read at most k pages per day over t vacation days. The maximum number of pages they can finish is the smaller of n and k * t. n = int(input()) k = int(input()) t = int(input()) print(min(n, k * t)) Shared Duty Schedule Two students clean on cycles of m and n days. The next time they coincide i ...

Counting GCD Pairs in Dynamic Multisets Maintain a multiset of positive integers with insertion and deletion operations. For each query, count unordered pairs (i, j) where i ≠ j and gcd(i, j) = k. Constraints: n, V ≤ 10^5. Conisder the change in answer count: $$\sum_{i=1}^{V}c_i[\gcd(i,x)=k]$$ Let x' = x/k: $$\sum_{i=1}^{\lfloor V/k \rfloor}c_{ ...

Efficient XOR Sum Calculation Define (f(i) = \oplus_{d|i}d), then compute (\oplus_{i=1}^{n}f(i)) for (n \le 10^{14}). Approach: Count occurrences of each number via floor division blocks and compute interval XOR sums. #include <bits/stdc++.h> using namespace std; using ll = long long; ll prefix_xor(ll x) { if (!x) return 0; ll re ...

This document presents an analysis of several competitive programming problems, outlining their descriptions, solution approaches, and specific implementation details or common pitfalls encountered. The problems cover various domains including number theory, combinatorics, geometry, and dynamic programming. Problem 1: Minimizing Sum with Given ...

Finding Perfect Numbers in C: A Complete Guide Understanding Perfect Numbers A perfect number is a positive integer that is equal to the sum of its proper divisors, excluding itself. For example, 6 is a perfect number because its divisors (1, 2, 3) sum to 6 (1+2+3=6). Other perfect numbers include 28, 496, and 8128. Perfect numbers have inte ...

Goldbach's Conjecture states that every even integer greater than or equal to 4 can be represented as the sum of two prime numbers. For a given even number $n$, we need to calculate the number of unique pairs $(p_1, p_2)$ such that $p_1 + p_2 = n$ and both $p_1, p_2$ are prime numbers. Algorithmic Strategy The maximum value for $n$ is $2^{15}$ ...