Problem 202: Laserbeam

Mathematical Foundation

Theorem (Unfolding Principle). A laser beam making $R$ reflections inside an equilateral triangle corresponds, via the standard unfolding technique, to a straight line in the triangular tessellation of the plane. The line starts at the origin and terminates at a lattice point $(a, b)$ in the oblique coordinate system, where $a + b = n$ with $n = (R + 3)/2$.

Proof. Each reflection off a mirror wall is equivalent to reflecting the triangle across that wall and continuing the beam in a straight line. After $R$ reflections, the beam has crossed $R$ triangle edges. The beam enters at vertex $C$ and must exit at a vertex, crossing $R$ edges total. In the oblique coordinate system where the three families of parallel lines in the tessellation are indexed by coordinates $(a, b)$ with $a + b = n$, the number of edge crossings for a line from $(0,0)$ to $(a,b)$ is $a + b - 2 + \text{adjustments for the entry/exit}$. Careful accounting (the beam enters through a gap, so the first and last crossings are at vertices, not interior edges) yields $n = (R + 3)/2$. For $R = 12017639147$, we get $n = 6008819575$. $\square$

Theorem (Exit Vertex Classification). The beam exits through vertex $C$ if and only if $b \not\equiv 0 \pmod{3}$ and $a \not\equiv 0 \pmod{3}$, which (given $a + b = n$ with $n \equiv 1 \pmod{3}$) is equivalent to $b \equiv 2 \pmod{3}$.

Proof. In the triangular tessellation, a lattice point $(a, b)$ corresponds to a copy of vertex $A$, $B$, or $C$ depending on the residues of $a$ and $b$ modulo 3. Specifically, the point is a copy of $C$ when $(a \bmod 3, b \bmod 3) \in \{(0,1),(1,0),(2,2)\}$… More precisely, the vertex type cycles with period 3 along each axis. Since $n = a + b \equiv 1 \pmod{3}$ and we require the endpoint to be a copy of $C$ (not $A$ or $B$), the condition reduces to $b \equiv 2 \pmod{3}$ (equivalently $a \equiv 2 \pmod{3}$). One can verify this directly for small cases. $\square$

Theorem (No Intermediate Vertex Condition). The beam passes through no intermediate vertex (and thus does not exit prematurely) if and only if $\gcd(a, b) = 1$, equivalently $\gcd(b, n) = 1$.

Proof. If $d = \gcd(a, b) > 1$, then the lattice point $(a/d, b/d)$ lies on the line segment from $(0,0)$ to $(a,b)$ and corresponds to a vertex of the tessellation. The beam would exit through that vertex before reaching $(a,b)$. Conversely, if $\gcd(a,b) = 1$, no intermediate lattice point lies on the segment. Since $a = n - b$, we have $\gcd(a,b) = \gcd(n-b, b) = \gcd(n, b)$. $\square$

Theorem (Counting via Mobius Inversion). The number of valid beam paths is:

where $C(d) = \#\{b \in [1, n-1] : d \mid b,\; b \equiv 2 \pmod{3}\}$, and $\mu$ is the Mobius function.

Proof. We seek $\#\{b \in [1, n-1] : \gcd(b, n) = 1,\; b \equiv 2 \pmod{3}\}$. By Mobius inversion, $\sum_{d \mid \gcd(b,n)} \mu(d) = [\gcd(b,n) = 1]$. Exchanging the order of summation:

For each squarefree divisor $d$ of $n$ with $\gcd(d, 3) = 1$, substituting $b = dk$ gives $k \in [1, n/d - 1]$ with $dk \equiv 2 \pmod{3}$, i.e., $k \equiv 2d^{-1} \pmod{3}$, yielding $C(d) = \lfloor(n/d - 1 - r)/3\rfloor + 1$ where $r = 2d^{-1} \bmod 3$. $\square$

Lemma (Factorization). $n = 6008819575 = 5^2 \times 11 \times 17 \times 23 \times 29 \times 41 \times 47.$ Since $3 \nmid n$, all $2^7 = 128$ squarefree divisors contribute.

Proof. Verified by trial division. Since $5^2 \mid n$, the Mobius function $\mu(d) = 0$ for any $d$ divisible by $5^2$, but we enumerate over squarefree divisors constructed from $\{5, 11, 17, 23, 29, 41, 47\}$. $\square$

Editorial

A laser beam enters vertex C of an equilateral triangle with mirrored sides, reflects exactly 12017639147 times off the internal surfaces, and exits through vertex C. Count the number of distinct beam paths. Approach: n = 6008819575 = 5^2 * 11 * 17 * 23 * 29 * 41 * 47. We factor n: primes = [5, 11, 17, 23, 29, 41, 47]. We then iterate over each subset T of primes. Finally, return count.

Pseudocode

Input: R = 12017639147
Output: number of valid laser paths
n = (R + 3) / 2 = 6008819575
Factor n: primes = [5, 11, 17, 23, 29, 41, 47]
count = 0
For each subset T of primes:
Return count

Complexity Analysis

• Time: $O(\sqrt{n})$ for factorization, plus $O(2^k)$ for the Mobius sum where $k = 7$ is the number of distinct prime factors. The Mobius summation is $O(128)$, dominated by factorization at $O(\sqrt{n}) \approx O(77{,}500)$.
• Space: $O(k) = O(7)$ to store the prime factors.

Answer

#include <bits/stdc++.h>
using namespace std;

int main(){
    // PE 202: Laser beam in equilateral triangle, R = 12017639147 reflections.
    // n = (R + 3) / 2 = 6008819575.
    // Count b in [1, n-1] with b ≡ 2 mod 3 and gcd(b, n) = 1.
    // Use Mobius inversion over squarefree divisors of n.

    long long R = 12017639147LL;
    long long n = (R + 3) / 2;  // 6008819575

    // Factor n
    vector<long long> primes;
    {
        long long tmp = n;
        for(long long p = 2; p * p <= tmp; p++){
            if(tmp % p == 0){
                primes.push_back(p);
                while(tmp % p == 0) tmp /= p;
            }
        }
        if(tmp > 1) primes.push_back(tmp);
    }

    int np = primes.size();
    long long ans = 0;

    for(int mask = 0; mask < (1 << np); mask++){
        long long d = 1;
        int bits = __builtin_popcount(mask);
        long long mu = (bits % 2 == 0) ? 1 : -1;
        for(int i = 0; i < np; i++){
            if(mask & (1 << i)) d *= primes[i];
        }

        if(n % d != 0) continue; // d must divide n

        long long nd = n / d;
        long long d_mod3 = d % 3;
        long long cnt = 0;

        if(d_mod3 == 0){
            // 3 | d => d*k ≡ 0 mod 3 ≠ 2. No valid k.
            cnt = 0;
        } else {
            long long dinv3 = (d_mod3 == 1) ? 1 : 2;
            long long r = (2 * dinv3) % 3;
            long long upper = nd - 1;
            if(r == 0){
                if(upper >= 3)
                    cnt = (upper - 3) / 3 + 1;
            } else {
                if(upper >= r)
                    cnt = (upper - r) / 3 + 1;
            }
        }

        ans += mu * cnt;
    }

    cout << ans << endl;
    return 0;
}

"""
Problem 202: Laserbeam

A laser beam enters vertex C of an equilateral triangle with mirrored sides,
reflects exactly 12017639147 times off the internal surfaces, and exits
through vertex C. Count the number of distinct beam paths.

Approach:
- Unfold reflections into a triangular tessellation.
- n = (R + 3) / 2 = 6008819575 is the lattice parameter.
- Count b in [1, n-1] with b ≡ 2 (mod 3) and gcd(b, n) = 1.
- Use Mobius inversion over squarefree divisors of n.

n = 6008819575 = 5^2 * 11 * 17 * 23 * 29 * 41 * 47
"""

def solve():
    R = 12017639147
    n = (R + 3) // 2  # 6008819575

    # Factor n (extract distinct primes)
    primes = []
    tmp = n
    p = 2
    while p * p <= tmp:
        if tmp % p == 0:
            primes.append(p)
            while tmp % p == 0:
                tmp //= p
        p += 1
    if tmp > 1:
        primes.append(tmp)

    np_ = len(primes)
    ans = 0

    # Inclusion-exclusion over squarefree divisors (Mobius function)
    for mask in range(1 << np_):
        d = 1
        bits = bin(mask).count('1')
        mu = 1 if bits % 2 == 0 else -1
        for i in range(np_):
            if mask & (1 << i):
                d *= primes[i]

        if n % d != 0:
            continue

        nd = n // d
        d_mod3 = d % 3

        if d_mod3 == 0:
            cnt = 0  # 3|d means d*k ≡ 0 mod 3, never ≡ 2
        else:
            dinv3 = pow(d, -1, 3)
            r = (2 * dinv3) % 3
            upper = nd - 1
            if r == 0:
                cnt = max(0, (upper - 3) // 3 + 1) if upper >= 3 else 0
            else:
                cnt = max(0, (upper - r) // 3 + 1) if upper >= r else 0

        ans += mu * cnt

    print(ans)

if __name__ == "__main__":
    solve()