poj2115--C Looooops(扩展gcd)

Description

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

  statement;

Input

Output

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

题目大意初始值是a，每一次加c ，可以对得到的值取模2^k，在值为b时结束，问最少会执行多少次，如过一直不会停FOREVER

由题中大意的到等式，假设一定会停，那么在循环x次后会等于b   也就是  （a + x*c）% （2^k）= b 。很明显的扩展gcd的题目，得到等式， a + c*x - b = y*(2^k) 也就是

求解 c*x - (2^k)*y = b-a ,问有没有整数解。

对于a*x1 + b*y1 = c ，用扩展gcd，求解 a*x1 + b*y1 = gad(a,b) = gcd(b,a%b)  = a*y2 +b* (x2-a/b*y2)得到  x1 = y2 , y1 = ( x2 +a/b*y2 ) , 利用这个等式，可以推到b = 0 时，那是x = 1 , y = 0 ,最大公约数为a，在逐层返回，最终得到 a*x1 + b*y1 = gad(a,b) 的解，如果c%( gcd(a,b) ) == 0 那么a*x1 + b*y1 = c有整数解，令d = gcd(a,b)，d = b / d.最小的正整数解围 x = ( x%d +ｄ )%d.

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
using namespace std;
void gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(b == 0)
    {
        d = a ;
        x = 1 ;
        y = 0 ;
    }
    else
    {
        gcd(b,a%b,d,y,x);
        y = -y ; x = -x ;
        y += a/b*x ;
    }
    return ;
}
int main()
{
    LL k , a , b , c , d , x , y ;
    while(scanf("%I64d %I64d %I64d %I64d", &a, &b, &c, &k)!=EOF)
    {
        if(a == 0 && b == 0 && c == 0 && k == 0)
            break;
        k = ( (LL)1 )<<k ;
        gcd(c,k,d,x,y);
        if( (b-a)%d )
            printf("FOREVER\n");
        else
        {
            x = (b-a)/d*x ;
            k = k/d ;
            x = (x%k+k)%k ;
            printf("%I64d\n", x);
        }
    }
    return 0;
}

poj2115--C Looooops(扩展gcd),布布扣,bubuko.com

poj2115--C Looooops(扩展gcd)

原文：http://blog.csdn.net/winddreams/article/details/38444561