2014
02-27

# Josephus Again

Traditional Joseph problem is n personal circle，from the first one to start to call the number. The number of people m back from the circle out until only left one person so far.
But now, we think about another Josephus problem. At the first, the circle includes n person. From the first one to start to call the number until call the m, we add a person beside the person who calls the number m, and the new person calls the number at the next round. Repeat this process, until k person in the circle. Now, label the n individuals, for the order of 1…n. The new added person label n+1…n+k by order. And we are interest in what the label the person whose rank is p.
To simplify the problem, we only think about when m=1. For example, N=3 and k=12, the circle is changed as follows:

Now ,the first one’s label is 1 and the second is 7,is third is 4,the forth is 8,the fifth is 2,the sixth is 9,the seventh is 5,the eighth
is 10,the ninth is 3,the tenth is 11,the eleventh is 6,the twelfth
is 12.

There many cases.
For every case:

The first line, two integer n(1<=n<=10^9),k(n<k<=10^9),q(1<=q<10^4),
N is the initial person, k is the final number of person, q is the number of query.
Then next q lines, every line contains an integer p as a query.
(1<=p<=k)

There many cases.
For every case:

The first line, two integer n(1<=n<=10^9),k(n<k<=10^9),q(1<=q<10^4),
N is the initial person, k is the final number of person, q is the number of query.
Then next q lines, every line contains an integer p as a query.
(1<=p<=k)

3 12 2
3
5

4
2
Hint
Hint: m is always 1.

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#define eps 1e-8
const double inf = 100000000000.0;
using namespace std;

long long Extended_Euclid(long long a, long long b, long long & x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = Extended_Euclid(b, a % b, x, y);
long long temp = x;
x = y;
y = temp - a / b*y;
return d;
}
long long a, b, c, x0, x2, y2, yy0;

double Min(double x, double y) {
return x < y ? x : y;
}

double Max(double x, double y) {
return x > y ? x : y;
}

bool ok(double x) {
if (fabs(x - (int) x) < eps) {
return 1;
}
return 0;
}

bool Mx(double y, double &x) {
x = double(-c - b * y) / a;
if (x >= x0 && x <= x2) {
return 1;
}
return 0;
}

bool My(double x, double &y) {
y = double(-c - a * x) / b;
if (y >= yy0 && y <= y2) {
return 1;
}
return 0;
}

int main() {
while (scanf("%lld%lld%lld%lld%lld%lld%lld", &a, &b, &c, &x0, &x2, &yy0, &y2) == 7) {
if (x0 > x2 || yy0 > y2) {
printf("0\n");
continue;
}
if (a == 0) {
if (b == 0) {
if (c == 0) {
printf("%lld\n", (x2 - x0 + 1)*(y2 - yy0 + 1));
} else
printf("0\n");
} else {
if (b > 0) {
if (yy0 * b <= (-c) && (-c) <= (y2 * b)) {
printf("%lld\n", (x2 - x0 + 1));
} else
printf("0\n");
} else {
if (yy0 * b >= (-c) && (-c) >= (y2 * b)) {
printf("%lld\n", (x2 - x0 + 1));
} else
printf("0\n");
}
}
} else {
long long ans;
if (b == 0) {
if (a > 0) {
if (x0 * a <= (-c) && (-c) <= (x2 * a)) {
printf("%lld\n", (y2 - yy0 + 1));
} else
printf("0\n");
} else {
if (x0 * a >= (-c) && (-c) >= (x2 * a)) {
printf("%lld\n", (y2 - yy0 + 1));
} else
printf("0\n");
}
} else {
long long d;
double xx, yy;
double x3 = -inf, x4 = inf;
if (Mx(yy0, xx)) {
x3 = Max(x3, xx);
x4 = Min(x4, xx);
}
if (Mx(y2, xx)) {
x3 = Max(x3, xx);
x4 = Min(x4, xx);
}
if (My(x0, yy)) {
x3 = Max(x3, x0);
x4 = Min(x4, x0);
}
if (My(x2, yy)) {
x3 = Max(x3, x2);
x4 = Min(x4, x2);
}

if (x3 == inf) {
printf("0\n");
continue;
}
long long x, y;
d = Extended_Euclid(a, b, x, y);
if (c % d != 0) {
printf("0\n");
continue;
}
x *= (-c / d);
b /= d;
if (b < 0)
b = -b;
x2 = x - (int((x - x3) / b)) * b;
x0 = x - (int((x - x4) / b)) * b;
if ((x2 > x3)) {
x2 -= b;
}
if (x0 < x4) {
x0 += b;
}
ans = (x2 - x0) / b + 1;

printf("%lld\n", ans);
}
}

}
return 0;
}

1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.