C Looooops POJ - 2115
扩展欧几里得算法
题目描述：算循环的次数，初始值为A，跳出循环的条件是A！=B，A每次+C，设所有的运算都是二进制k位数，运用补码的原理，当x=2^k,则x+1溢出后=1.
解题思路：扩展欧几里得算法。推一下方程，令所求的次数为x (A+Cx)%2^k=B ->
A+Cx=2^k*y+B ->移项得Cx-2^k*y=B-A; 将各参数代入函数即可。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
long long ans=exgcd(b,a%b,x,y);
long long t=y;
y=x-(a/b)*y;
x=t;
return ans;
}
int main()
{
int A,B,C,K;
while(scanf("%d %d %d %d",&A,&B,&C,&K)==4&&(A||B||C||K))
{
long long a=C,b=(long long)1<<K,c=B-A,x,y;
long long gcd=exgcd(a,b,x,y);
if(c%gcd)
{
printf("FOREVER\n");
}
else
{
long long x0=x*(c/gcd)%(b/gcd);
x=(x0+(b/gcd))%(b/gcd);
printf("%I64d\n",x);
}
}
return 0;
}
投递腾讯等公司10个岗位 >