Computing Valid Offsets for Invariant Greatest Common Divisor Using Euler's Totient Function
Problem Definition
Given two positive integers base and modulus where base < modulus, determine the count of non-negative integers x such that 0 ≤ x < modulus and gcd(base, modulus) == gcd(base + x, modulus).
Input Constraints
Number of test cases: 1 ≤ T ≤ 50
Value range: 1 ≤ base < modulus ≤ 10^{10}
Mathematical Reduction
Let d = gc ...
Posted on Thu, 06 Aug 2026 16:53:53 +0000 by woza_uk