POJ 2115 - C Looooops | 眈眈探求

算法

原创

发布日期: 2011-08-01

更新日期: 2026-11-05

文章字数: 1.2k

阅读时长: 6 分

阅读次数:

POJ 2115 - C Looooops
Time: 1000MS
Memory: 65536K
难度: 初级
分类: 同余模

0x00 POJ 原题

Description

A Compiler Mystery: We are given a C-language style for loop of type

for (variable = A; variable != B; variable += C)

  statement;

I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2^(k)) modulo 2^(k).

Input

The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2^(k)) are the parameters of the loop.

The input is finished by a line containing four zeros.

Output

The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.

Sample Input

Sample Output

0
2
32766
FOREVER

Source

CTU Open 2004

0x10 题目概述

对于 C 的 for(i=A ; i!=B ;i +=C) 循环语句，问在 k 位存储系统中循环几次才会结束。

若在有限次内结束，则输出循环次数。

否则输出死循环。

0x20 解题思路

题意不难理解，只是利用了 k 位存储系统 的数据特性进行循环。

例如 int 型是 16 位的，那么 int 能保存 2^16 个数据，即最大数为 65535（本题默认为无符号），

当循环使得 i 超过 65535 时，则 i 会返回 0 重新开始计数

如 i=65534，当 i+=3 时，i=1

其实就是 i=(65534+3)%(2^16)=1

有了这些思想，设对于某组数据要循环 x 次结束，那么本题就很容易得到方程：

x = [(B-A+2^k)%2^k] / C

即 Cx=(B-A)(mod 2^k) 此方程为 模线性方程，本题就是求 X 的值。

下面将结合《算法导论》第 2 版进行简述，因此先把上面的方程变形，统一符号。

令：

a = C
b = B-A
n = 2^k

那么原模线性方程变形为：

ax = b (mod n)

该方程有解的充要条件为 gcd(a,n) | b，即 b % gcd(a,n) == 0

令 d = gcd(a,n)

有该方程的最小整数解为 x = e (mod n/d)

其中 e = [x0 mod(n/d) + n/d] mod (n/d)，x0 为方程的最小解

那么原题就是要计算 b % gcd(a,n) 是否为 0，若为 0 则计算最小整数解，否则输出 FOREVER

当有解时，关键在于计算最大公约数 d = gcd(a,n) 与 最小解 x0

参考《算法导论》，引入欧几里得扩展方程 d=ax+by，

通过 EXTENDED_EUCLID 算法（P571）求得 d、x、y 值，其中返回的 x 就是最小解 x0，求 d 的原理是辗转相除法（欧几里德算法）

再利用 MODULAR-LINEAR-EQUATION-SOLVER 算法（P564）通过 x0 计算 x 值。

注意 x0 可能为负，因此要先 + n/d 再 模 n/d。

以上方法的推导过程大家自己看《算法导论》。。。这里不证明，只直接使用。

注意：

计算 n=2^k 时，用位运算是最快的，1<<k （1 左移 k 位）就是 2^k
但是使用 long long 的同学要注意格式， 1LL<<k
使用 __int64 的同学要强制类型转换 (__int64)1<<k

不然会 WA

0x30 测试数据

来源：CTU Open 2004（问题 C）
下载：download
输入：input
输出：output

0x40 AC 源码

//Memory Time 
//212K   0MS 

#include<iostream>
using namespace std;

//d=ax+by,其中最大公约数d=gcd(a,n)，x、y为方程系数，返回值为d、x、y
__int64 EXTENDED_EUCLID(__int64 a,__int64 b,__int64& x,__int64& y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;  //d=a，x=1,y=0,此时等式d=ax+by成立
    }
    __int64 d=EXTENDED_EUCLID(b,a%b,x,y);
    __int64 xt=x;
    x=y;
    y=xt-a/b*y;  //系数x、y的取值是为满足等式d=ax+by
    return d;
}

int main(void)
{
    __int64 A,B,C,k;
    while(scanf("%I64d %I64d %I64d %I64d",&A,&B,&C,&k))
    {
        if(!A && !B && !C && !k)
            break;

        __int64 a=C;
        __int64 b=B-A;
        __int64 n=(__int64)1<<k;  //2^k
        __int64 x,y;
        __int64 d=EXTENDED_EUCLID(a,n,x,y);  //求a,n的最大公约数d=gcd(a,n)和方程d=ax+by的系数x、y

        if(b%d!=0)  //方程 ax=b(mod n) 无解
            cout<<"FOREVER"<<endl;
        else
        {
            x=(x*(b/d))%n;  //方程ax=b(mod n)的最小解
            x=(x%(n/d)+n/d)%(n/d);  //方程ax=b(mod n)的最整数小解
            printf("%I64d\n",x);
        }
    }
    return 0;
}