扩展欧几里得模板 poj-C Looooops_扩展欧几里得 type:c-CSDN博客

本文链接：https://blog.csdn.net/acblacktea/article/details/49982457

poj撸了三个专题了虽然前几个很难但还可以自己想出来，到数论这都是坎，只能看题解慢慢学了。。。
总结下知识点
1 欧几里得定理 GCD（a,b) = GCD(b，a%b) 代码实现渣渣我都能毫不思考的打出来了。
2 ax+by = gcd(a,b)有解同理可推出 ax+by=c有解的充要条件是c%gcd(a,b)=0;
ax+by=gcd(a,b)通解为x = x0+b/gcd(a,b)*t,y = y0-a/gcd(a,b)*t,这公式可以求出所有的解，x0+bt则不能，可以自己想出来；
3核心是欧几里得的扩展
(1) ax+by = gcd(a,b);
bx1+a%by1 = gcd(b,a%b) = gcd(a,b) = ax+by;
bx1+(a-a/b*b) *y1 = ax+by
ay1+b(x1-a/b*y1) = ax+by
x = y1;
y = x1-a/b*y1;
此公式递推出x,y;
（2）递推肯定有起点，起点是gcd(a,b)x+0*y=gcd(a,b)
此时y=0,x=1; 当然y也可以是别的乱七八糟的，但0更省事；
(3)最后求出x 通解为x+b/gcd(a,b)*t, t为任意整数

int x,y;
int e_gcd(int a,int b)
{
    if(b==0)
    {
       x = 1;
       y = 0;
       return a;
    }
    int ans = e_gcd(b,a%b);
    int t = x;
    x = y;
    y = t-a/b*y;
    return ans;
}  //求通解

//by blacktea 11/22/2015
//扩展欧几里得模板
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
__int64 a,b,c,k,x,y;
__int64 e_gcd(__int64 a,__int64 b)
{
    if(!b){
         x = 1;
         y = 0;
         return a;
    }
    __int64 ans = e_gcd(b,a%b);
    __int64 t =x;
    x = y;
    y = t-a/b*y;
    return ans;
}
//扩展欧几里得核心代码
int main()
{
    while(scanf("%I64d %I64d %I64d %I64d",&a,&b,&c,&k))
    {
        if(!a&&!b&&!c&&!k)break;
        __int64 mod = (__int64)1<<k;
        __int64 g = e_gcd(c,mod);
        if((b-a)%g)printf("FOREVER\n");
        else
        {
            x=(b-a)/g*x;
            __int64 s=mod/g;
            x = (x%s+s)%s;//求x所有解中的为正数中的最小值 同时考虑x起始为负的情况
            printf("%I64d\n",x);
        }
    }
    return 0;
}