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 qddpx at 2012-08-15 23:23:33 on Problem 2115
```不过还是没1A，注意有a==b,c=0的情况

#include <cstdio>
typedef long long ll;

ll a, b, c, k, d, m;

ll extEuc(ll m, ll k) {
long long *u, *v, *t, a[3][3] = {1, 0, m, 0, 1, k}, q;
u = (m > k) ? a[0] : a[1];
v = (m > k) ? a[1] : a[0];
t = a[2];
while(v[2] != 1) {
q = u[2] / v[2];
t[0] = v[0], t[1] = v[1], t[2] = v[2];
v[0] = u[0]-q*v[0], v[1] = u[1]-q*v[1], v[2] = u[2]-q*v[2];
u[0] = t[0], u[1] = t[1], u[2] = t[2];
}
while(v[1] < 0) v[1] += m;
return v[1] % m;
}

int main() {
while(scanf("%lld%lld%lld%lld", &a, &b, &c, &k) && k) {
m = 1LL << k, d = (b - a + m) % m;
if(!d && !c){
printf("0\n");
continue;
}
while(!(d&1) && !(c&1))
d >>= 1, c >>= 1, m >>=1;
if(!(c&1)) {
printf("FOREVER\n");
continue;
}
printf("%lld\n", extEuc(m, c) * d % m);
}
return 0;
}```

Followed by: