首页 > 代码库 > POJ - 2115C Looooops 扩展欧几里得（做的少了无法一眼看出）

POJ - 2115C Looooops 扩展欧几里得（做的少了无法一眼看出）

2024-09-23 21:35:47   215人阅读

题目大意&&分析：

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

  statement;
这个循环式子表示a+c*n（n为整数）==b是停止循环，题目中要求（a+c*n）%2^k=b时停止循环；所以我们可以得到一个形如ax+by=c的方程式：a+c*n=b+2^k*m；
通过移项：c*x-2^k*m=b-a；
可以直接套exgcd模板了：

代码：
#include <iostream>

using namespace std;
typedef long long ll;
ll d;
ll x,y;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if (!b)
    {
        x=1;y=0;d=a;return ;
    }
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=(a/b)*x;
    }
}
int main()
{
    ll a,b,c,k;
    while (cin>>a>>b>>c>>k&&(a+b+c+k))
    {
        ll C=(ll)1<<k;                //注意别写成ll k=(ll)1<<k; 会出错就是了；

        exgcd(c,C,d,x,y);
        //cout<<x<<y<<endl;
        if ((b-a)%d)
        {
            cout<<"FOREVER"<<endl;
        }
        else
        {
            x=x*(b-a)/d;
            C/=d;                    //1
            x=(x%C+C)%C;              //2
            cout<<x<<endl;
        }
    }
}

这两行用于求出最小正整数解，ax+by=c;  a,b互素，则ax1+by1=ax2+by2；那么（x1-x2）一定是b的整数倍，

所以当x>0时，x%b即为所求；

x<0时，x%b+b即为所求，二者综合就是（x%b+b）%b可以得出最小正整数解；

POJ - 2115C Looooops 扩展欧几里得（做的少了无法一眼看出）


联系
我们