POJ 2115 C Looooops(扩展欧几里得应用)

题目地址:POJ 2115

水题。

公式非常好推。最直接的公式就是a+n*c==b+m*2^k.然后能够变形为模线性方程的样子,就是

n*c+m*2^k==b-a.即求n*c==(b-a)mod(2^k)的最小解。(真搞不懂为什么训练的时候好多人把青蛙的约会都给做出来了,这题却一直做不出来。。

这两道不都是推公式然后变形吗。

。。。。

代码例如以下:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm> using namespace std;
#define LL __int64
LL X, Y;
LL exgcd(LL a,LL b)
{
if(b==0)
{
X=1;
Y=0;
return a;
}
LL r=exgcd(b,a%b);
LL t=X;
X=Y;
Y=t-a/b*Y;
return r;
}
int main()
{
LL a, b, c, k, d, L, z;
while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k)!=EOF&&k)
{
z=pow(2,k);
d=exgcd(c,z);
L=b-a;
if(L%d)
{
printf("FOREVER\n");
continue ;
}
else
{
LL ans=X*L/d;
LL s=z/d;
if(ans<0)
{
ans=ans%s+s;
}
else
{
ans=ans%s;
}
printf("%I64d\n",ans);
}
}
return 0;
}
上一篇:PHP 错误与异常 笔记与总结(7)将错误日志以邮件方式发送


下一篇:POJ 2115 C Looooops(模线性方程)