After looking at the hints for 1925B (https://codeforces.net/problemset/problem/1925/B), I realized the solution by knowing the properties of gcd(a,b) = gcd(a, a + b). But since this is codeforces, I'm wondering how I would have got to the solution if I hadn't known this property about gcd. For those who have solved this without using mathematical properties, how did you solve this?