POJ 2115 C Looooops(模线性方程)

http://poj.org/problem?id=2115

题意:

给你一个变量,变量初始值a,终止值b,每循环一遍加c,问一共循环几遍终止,结果mod2^k.如果无法终止则输出FOREVER。

思路:

根据题意原题可化成c * x = b - a mod (2 ^ k),然后解这个模线性方程。

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF=0x3f3f3f3f;
const int maxn=+; int a,b,c,k; void gcd(ll a,ll b,ll& d,ll& x,ll& y)
{
if(!b) {d=a;x=;y=;}
else
{
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
} ll modeq(ll a,ll b,ll n)
{
ll e,i,d,x,y,f;
gcd(a,n,d,x,y);
if(b%d) return -;
else
{
f=n/d<?(-*n/d):n/d;
e=(x*(b/d)%f+f)%f;
return e;
}
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(~scanf("%d%d%d%d",&a,&b,&c,&k) && a+b+c+k!=)
{
ll n=b-a;
ll m=1LL<<k;
ll ans = modeq(c,n,m);
if(ans==-) puts("FOREVER");
else printf("%lld\n",ans);
}
return ;
}
上一篇:POJ 2115 C Looooops(扩展欧几里得应用)


下一篇:HDU1269 迷宫城堡