[原创]POJ 2115 C Looooops [扩展欧几里得]【数论】[水]

2016-09-13 12:29:47 Tabris_ 阅读数：405

博客爬取于2020-06-14 22:43:21
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52524819

题目链接:http://poj.org/problem?id=2115
----------------------------------.
C Looooops
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 24028 Accepted: 6658
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 < 2k) modulo 2k.

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 < 2k) 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

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
Sample Output

0
2
32766
FOREVER
Source

CTU Open 2004

------------------------------------------------------.
题目大意 :
就是 给你a,b,c,k
问你这个循环 能不能被跳出 能的话跳出所需的最小循环次数是多少
for (variable = A; variable != B; variable += C)

其实稍转化下就是这个了
在方程a+xc≡b(mod 2^k)中求取x的最小正整数解

解题思路 :
根据题意很明显的知道
a+xc=b+y(2^k)
然后移项 就得到了这么一个标准的二元一次不定方程
b-a=xc-y(2^k)
最后扩展欧几里得求解一下就行了

求解出来的数应该是这样
(c,2^k)=xc-y(2^k)
设(c,2^k) = d;

然后原式就改成了这样
(b-a)/dxc-(b-a)/ry*(2^k)=b-a

结果就是
x = (b-a)/d*x;
最后去一下最小整数解
x = (x%(2^k)+(2^k))%(2^k);

如果是最小正整数解得话 还得
if(x==0) x=2^k;

!!!最最重要的是POJ交G++要用I64 然而VJ上告诉的是lld WA了无数发 还是最后看了代码才知道5555555555555

附本题代码
----------------------------------.

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f
# define pb push_back

# define lalal puts("*******");
/*************************************/

const int MOD = 1e9+7;
const int M = 1e5+10;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        LL r = exgcd(b,a%b,x,y);
        LL t = x;
        x = y;
        y = t - (a/b)*y;
        return r;
    }
}

int main()
{
    LL a,b,c,k;
    while(~scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k)&&(a||b||c||k))
    {
        bool flag = 0;
        LL x,y;
        LL r = exgcd(c,(1ll<<k),x,y);
        if((b-a)%r) flag = 1;
        else
        {
            LL tem = (1ll<<k)/r;
            x=(b-a)/r*x;      //解
            x=(x%tem+tem)%tem;//最小正整数解
        }
        //printf("%lld %lld %lld\n",r,x,y);

        if(flag)    puts("FOREVER");
        else    printf("%I64d\n",x);
    }
    return 0;
}