传送门:POJ 2115 - C Looooops

题目大意:

给你一个 $C$语言中的 $for$ 循环伪代码,如下:

1
2
for (variable = A; variable != B; variable += C)
statements;

varibale是变量名,所有数据的类型都是一个 $k$ 位的无符号整数,给你 $A,B,C,k$ 的值,问你要这个循环会执行多少次后退出。

解题思路:

我们知道在 $C$语言中,如果一个数超过了它的上界,那么会从下界重新开始,同样如果超过了下界也是一样会从上界重新开始。
比如说,int类型的范围是 $[-2147483648,2147483647]$。有如下代码:

1
2
int int_max = 2147483647;
cout << int_max + 1 << endl;

输出如下:

1
-2147483648

可以看出数值从上界超出后回到了下界,这样这道题就很好去算了,设循环会执行 $x$ 次,我们可以根据题意列出一个等式:
$(A+Cx)%2^k=B$
变形一下成为我们需要的形式:
$Cx+2^ky=B-A$
这里 $y$ 的值不重要,就是表示一下 $2^k$ 的倍数使等式成立。
我们需要的是 $x$,因为循环次数肯定是非负的,所以我们要去计算这个等式的 $x$ 解的最小的非负解。
分析到这里,这个题就很明显了,是一个扩展欧几里得求解二元一次方程的板子题,然后在把 $x$ 算一下最小非负的值就搞定了。
然后就是解方程的时候如果发现没有整数解,那就是 FOREVER 的情况了。

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
ll q = exgcd(b, a % b, y, x);
y -= a / b * x;
return q;
}
bool eqa_solve(ll &x, ll &y, ll a, ll b, ll c)
{
ll q = exgcd(a, b, x, y);
if (c % q != 0)
return false;
ll tms = c / q;
x *= tms;
y *= tms;
ll m = b / q;
x = (x % m + m) % m; // 这句就是把 x 变为最小的非负整数解
return true;
}
int main(void)
{
ll a, b, c, k;
while (cin >> a >> b >> c >> k && k)
{
ll x, y, m = (ll)1 << k;
if (eqa_solve(x, y, c, m, b - a))
cout << x << endl;
else
cout << "FOREVER" << endl;
}
return 0;
}