POJ2115 C-Loop

这道题是求解不定方程的一道好练习题。

题目描述的很诡异……还说什么k进制，其实就是要求一个数A，每次加C，问到B要加多少次，所有的数对2^k取模。

也就是说我们能列出如下方程：A+xC ≡ B （mod 2^k）
我们把这个方程两边移项转化，那么就能得到一个不定方程的形式。

老套路，判断有没有解，否则用exgcd求解。

本题有小坑，你在1<<32的时候，即使变量开了longlong也不行，必须写成1ll的形式，否则会WA。

看一下代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<set>

#include<vector>

#include<queue>

#define pb push_back

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = ;

const int N = ;

const int INF = ;

const ll mod = ;

ll read()

{

    ll ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

    if(ch == '-') op = -;

    ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

    ans *= ;

    ans += ch - '';

    ch = getchar();

    }

    return ans * op;

}

ll a,b,c,k,x,y,p,q,s;

ll gcd(ll a,ll b)

{

    return (!b) ? a : gcd(b,a%b);

}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    if(!b)

    {

    x = ,y = ;

    return a;

    }

    ll d = exgcd(b,a%b,y,x);

    y -= a/b * x;

    return d;

}

int main()

{

    while()

    {

    a = read(),b = read(),c = read(),k = read();

    if(!a && !b && !c && !k) break;

    p = c,q = 1LL << k,s = (b-a+q) % q;

    ll G = gcd(p,q);

    if(s % G)

    {

        printf("FOREVER\n");

        continue;

    }

    p /= G,q /= G,s /= G;

    exgcd(p,q,x,y);

    x = (x + q) % q,x *= s,x %= q;

    printf("%lld\n",x);

    }

    return ;

}

巴特西

POJ2115 C-Loop

最新文章

热门文章