首页 > ACM题库 > HDU-杭电 > HDU 3042-Josephus Again-数论-[解题报告]HOJ
2014
02-27

HDU 3042-Josephus Again-数论-[解题报告]HOJ

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:  
Bee

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.

这题各种需要注意,wa了好多次,扩展欧几里得求出每两个整点之间x或者y的距离,然后求解。关键是找到直线上的一个整点,再通过这个整点找到距离直线与矩形交点最近的整点。然后计算个数。


#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;
}
 

参考:http://zhulinb123.blog.163.com/blog/static/18441404320125200282628/


  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.