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; }