# POJ 2115 C Looooops

Problem Description:
You have a for loop that looks like this:
for (value_type i = A; i != B; i += C) ;
, where value_type is K-bits unsigned integer data type.
You want to know whether the loop will reach an end, and if it will, the number of increments.

Constraints:
1 ≤ K ≤ 32
0 ≤ A, B, C < 2**K

Solution:
Essentially we want to find the smallest positive integer x such that: holds.
With extended euclidean algorithm, we can find some x and y that satisfies the above.
To get the minimum x that satisfies some ax + by = c, we need only to have some arbitrary solution x', then x = x' % (b / gcd(a, b)).

Code:

```#include <iostream>
#include <algorithm>

long long A, B, C, K;

long long ext_gcd(long long a, long long &x, long long b, long long &y) {
if (!b) return x = 1, y = 0, a;
long long xx, yy;
long long g = ext_gcd(b, xx, a % b, yy);
x = yy;
y = xx - a / b * yy;
return g;
}

signed main() {
std::ios::sync_with_stdio(false);
while (std::cin >> A >> B >> C >> K && K) {
long long a = C, b = 1LL << K, c = B - A;
long long x, y;
long long g = ext_gcd(a, x, b, y);
if ((a == 0 && c) || c % g) std::cout << "FOREVER" << std::endl;
else std::cout << ((x * (c / g) % b + b) % (b / g)) << std::endl;
}
return 0;
}
```