Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这就是一道扩展欧几里德 就不知哪里错 郁闷哦

Posted by 1325784226 at 2012-05-01 20:28:40 on Problem 2115
```#include <cstdio>
__int64 pow(__int64 a,__int64 b)
{
__int64 s=1;
for(__int64 i=0; i<b; i++)
s *= a;
return s;
}

__int64 exGcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
__int64 r = exGcd(b,a%b,x,y);
__int64 t = x;
x = y;
y = t - a/b * y;
return r;
}

int main()
{
//freopen("input.txt","r",stdin);
__int64 a,b,c,k;
__int64 x,y;
__int64 p;
__int64 d;
__int64 ab;
__int64 r;
while(scanf("%I64d %I64d %I64d %I64d",&a,&b,&c,&k)!=EOF && a != 0 && b!=0 && c !=0 && k != 0)
{
p = pow(2,k);
ab = b - a;
d = exGcd(c,-p,x,y);
if(ab % d !=0)
printf("FOREVER\n");
else
{
r = ab / d;
__int64 xx = r*x;
if(xx < 0)
xx = (xx % (p/d) + (p/d))% (p/d);

printf("%I64d\n",xx);
}

}
return 0;
}```

Followed by: