Problem Solving Journal 3

Published Oct 13, 2025

Problems: Modular Tetration · 1-Regular Subgraphs of 2-Regular Directed Graphs · Propagation Queries on Trees, Revisited

Over the summer I indeed made it to Master on Codeforces, was quite happy about it. Still, Master isn’t nearly good enough to make it to ICPC WF or even qualify for the UBC team (there’s many strong people here). I’m first hoping I can make the team and then my goal will be to reach Grandmaster level by the time NAC comes around. I think I have the aptitude for GM.

Unfortunately my math olympiad skill has greatly deteriorated since high school. I don’t want to practice but I don’t want to regress on Putnam, that would be quite sad. Current plan is to lightly practice and see :)

I am too lazy to write things up which is why this “journal” is so infrequently updated.

Modular Tetration

For a positive integer a, we define a recurrence $\{b_n\}$ as $b_n=a^{b_{n−1}}$, with $b_0=1$.

We say that a positive integer $a$ is $m$-tetrative if the sequence $b$ stabilizes to 1 modulo $m$, that is, there exists $N \geq 0$ such that $b_n \equiv 1 \pmod{m}$ for all $n \geq N$.

For a given $m$, calculate the density of the $m$-tetrative integers. $m \leq 10^{18}$ is given as a product of integers $m = xyz$, where $x, y, z \leq 10^6$.

Here, the density of a set $S$ is the limit $\lim_{n \to \infty} \frac{|S \cap [1, 2, \dots, n]|}{n}$. Informally, it is the “proportion” of positive integers that are $m$-tetrative.

You should find this in $\mathcal{O}(\text{polylog } m)$ time.

—Source: Codeforces 2147G

Solution

First we do some number theory to characterize the $m$-tetrative integers.

Consider the convergence of $b_n \pmod m$. We require

This means that $\gcd(m, \text{ord}_m(a)) = 1$, and $\text{rad } \text{ord}_m(a) \mid a$, where $\text{rad}$ is the radical. Of course, we also require $\gcd(a, m) = 1$. We can see that these three conditions are necessary, but actually also sufficient. The tetration process guarantees that $b_n$ eventually converges to $0 \pmod{\text{ord}_m(a)}$, at which point $b_n \equiv 1 \pmod m$ is guaranteed.

That was the easy part, now we try to find the density of $m$-tetrative integers. Let us fix $k = \text{rad } \text{ord}_m(a)$, and then if some $a$ is $m$-tetrative with order radical $k$, then $k \mid a$. But $k \mid a + tm \iff k \mid t$. So considering $a \mod m$, the densitiy of this equvalence class is $1/k$. Therefore, we are looking to find

Where $\text{count }{k}$ is the number of residues with $\text{rad } \text{ord}_m(a) = k$.

CRT Decomposition

First let’s try this using Chinese Remainder Theorem (CRT) decomposition to enumerate $\text{count}(k)$. Write $s = \text{ord}_m(a)$. We know that given $m = \prod p_i^{\alpha_i}$, since $\gcd(m, s) = 1$ and $s \mid \phi(m)$ it must be the case that $s \mid \prod (p_i - 1)$. We can decompose $s = \prod s_i$ where $s_i \mid p_i - 1$. However, we can enforce $s_i = \text{ord}_{p_i^{\alpha_i}}(a)$, since $\text{ord}_{p_i^{\alpha_i}}(a) \mid \phi(p_i^{\alpha_i})$.

Then the question is, how many $a \mod p_i^{\alpha_i}$ have order $s_i$? The answer is $\phi(s_i)$. This is trivial for $p_i = 2$, and for other primes we note that $(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z})^{\times}$ is cyclic, so it follows by considering powers of a primitive root. Therefore, this $s_i$ contributes $\frac{\phi(s_i)}{\text{rad } s_i}$. We can do this for each $s_i$, and take a direct product by combining

The denominator gets the new radical of the new order $s$ of each $a$ from the CRT. Done correctly this is a $O(\prod d(s_i))$ solution, which we know can be $o((\text{rad } m)^{\epsilon})$, but in practice computing and storing the direct sums can take a lot of memory.

Sylow Decomposition

We can try to a different way of resolving $\text{count }{k}$. The key here is the fact that for each Sylow $p$-subgroup $S_p$ of $(\mathbb{Z}/m \mathbb{Z})^{\times}$,

Which is extremely useful here, because we now note that we can instead consider the count over subsets of $k = \prod q_j$ for $\phi(m) = \prod q_i^{\beta_i}$.

What’s left is to recover $\text{count } k$, which is an immediate application of mobius inversion. In fact at this point we know we are done since the set of multiplicative functions is a group under Dirichlet convolution. We therefore must obtain a multiplicative function, so we can easily calculate it after a prime sieve.

And since the possible $k$ is a set of divisors, iterating over possible $k$ we also get something nice.

Where $K = \text{rad } \phi(m)/\gcd(\text{rad } \phi(m),\text{rad } m)$. Of course we can prime sieve this and then compute the answer in $\mathcal{O}(\text{polylog } m).$$\blacksquare$

This is the first time I really got the chance to use university math on a CP problem and was also my first LGM (3000+) rating solve!!!

1-Regular Subgraphs of 2-Regular Directed Graphs

Given a 2-regular directed graph $G$ on $n$ vertices, how many 1-regular directed subgraphs does it have?

Specifically, show that it is a power of two greater than 1.

—USA TSTST 2018 Problem 2

We construct the bipartition $H_{n, n}$, with edge $(u, v)$ if and only if u has a directed edge to $v$. Although an injective mapping from the orignal graph, this helps to see the existance of such a subgraph, in the form of a perfect matching that corresponds to the original graph!

Note that each vertex in $H$ has degree $2$, so we can appeal to Hall’s Marriage Theorem and the pigeonhole principle to show that $|W| \leq |N_H(W)|$. Note that the complement subgraph of any 1-regular subgraph is also 1-regular, it remains to prove the powers of two condition.

To realize the powers of two, here is a nice linear algebraic way to force it in $\mathbb{F}_2$. We can associate with each edge an binary variable $x_i$ of whether it is in the subgraph. Then for each node we have two linear restraints: the outgoing edges sum to $1$ and incoming edges sum to $1$.

Therefore this system is a $2n \times 2n$ linear system in $\mathbb{F}_2$, and so its solution space is an affine vector space. Thus we are done! $\blacksquare$

Propagation Queries on Trees, Revisited

Half a year ago in my first problem solving journal I outlined a cool approach for supporting “propagation queries” on trees. However, it didn’t fully work because I had yet to learn data structures that support efficient path arithmetic with updates on trees.

I recently learned Heavy-Light Decomposition, and now the approach works! This led me to solve a 3200 in less than an hour.

You have a rooted tree on $n$ vertices, with binary labels. Initially all the nodes are white. Support these query operations efficiently:

1. Given some node, if it is white mark it black, if it is already black repeat this operation on all its children.
2. Given some node, mark all subtrees of this node white.
3. Given some node, find its color.

—Source: Codeforces 1017G

Solution

Read the original post!

We no longer try Euler tour but instead use Heavy-Light Decomposition (HLD) to support the root path suffix maximums.

What we can do now is initialize all nodes to $-1$, update the node values using HLD by adding $1$ and compute suffix maximums with HLD and the corresponding Lazy segment tree, with the sign determining color. This supports query 1 and query 3. Query 2 on vertex $v$ is easy to add, simply reset all $v$ subtree values in the segment tree to -1, then perform query 3 on $v$. If the answer is $x \geq 0$, subtract $x + 1$ from $v$ to reset it. $\blacksquare$

This was a 3200 problem that I solved in under an hour!