首页 > > 程序设计 > C/C++ >

POJ 2115 C Looooops扩展欧几里得

2018-06-17 23:43:15来源：未知阅读 ()

题意不难理解，看了后就能得出下列式子：

　　(A+C*x-B)mod(2^k)=0

　即(C*x)mod(2^k)=(B-A)mod(2^k)

　利用模线性方程(线性同余方程)即可求解

　模板直达车

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
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 r = exgcd(b, a%b, y, x);
   ll t = x;
   y = y - a/b*t;
   return r;
}
bool modular_linear_equation(ll a, ll b, ll n) {
    ll x, y, x0, i;
    ll d = exgcd(a, n, x, y);
    if (b%d)
    {
        printf("FOREVER\n");
        return false;
    }
    x0 = x*(b/d)%n; //x0为方程的一个特解，可以为正也可以为负。题目要求的是最小的非负数
    ll ans;
    if(x0<0)
    {
        ans=x0;
        for(i = 0;ans<0; i++)
            ans=(x0 + i*(n/d))%n;
    }
    else
    {
        ans=x0;
        ll temp;
        for(i=0;ans>=0;i++)
        {
            temp=ans;
            ans=(x0 - i*(n/d))%n;
        }
        ans=temp;
    }
    printf("%I64d\n",ans);
    return true;
}
int main()
{
    //freopen("in.txt","r",stdin);
    ll A,B,C,k;
    while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&k))
    {
        if(A==0 && B==0 && C==0 && k==0)
            break;
        ll k2=(ll)1<<k;
        if(A==B)
            printf("0\n");
        else
        modular_linear_equation(C,B-A,k2);
    }
    return 0;
}