标签: 类欧几里得算法

  • 雅礼集训Day10 T3 加农炮

    好好看文件名!!!

    直接在Stern Brocot树上走,每次走到一个点,通过类欧几里得求出来这个斜率的直线左侧的整点个数。

    然后二分在Stern Brocot树上向左或者向右跳。

    复杂度$O(Tlog^3n)$

    $$ \text{求}\frac{x}{y}<\frac{a}{b},x\in \left[ \text{1,}n \right] \cap \text{Z,}y\in \left[ \text{1,}m \right] \cap \text{Z的}\frac{x}{y}\text{个数。} \\ \text{式子变形得到} \\ x<\frac{ay}{b} \\ xb<ay \\ \text{考虑直接枚举}x,\text{则可得}\sum_{1\le x\le n}{\sum_{1\le y\le m}{\left[ y>\frac{bx}{a} \right]}} \\ =\sum_{1\le x\le n}{\sum_{1\le y\le m}{\left[ y>\lfloor \frac{bx}{a} \rfloor \right]}} \\ =\sum_{1\le x\le n}{\left( m-\lfloor \frac{bx}{a} \rfloor \right) \left[ m>\lfloor \frac{bx}{a} \rfloor \right]} \\ \text{由}m>\lfloor \frac{bx}{a} \rfloor \text{可得}m>\frac{bx}{a}\text{,进而}ma>bx \\ \text{可得}x<\frac{ma}{b},\text{即}x<\lceil \frac{ma}{b} \rceil ,\text{即}x\le \lceil \frac{ma}{b} \rceil -1 \\ \text{故原式等价于}\sum_{1\le x\le \min \left( n,\lceil \frac{ma}{b} \rceil -1 \right)}{m-\lfloor \frac{bx}{a} \rfloor} \\ =m\times \min \left( n,\lceil \frac{ma}{b} \rceil -1 \right) -\sum_{1\le x\le \min \left( n,\lceil \frac{ma}{b} \rceil -1 \right)}{\lfloor \frac{bx}{a} \rfloor} \\ \text{考虑如何计算}f\left( n,a,b,c \right) =\sum_{0\le i\le n}{\lfloor \frac{ai+b}{c} \rfloor} \\ f\left( n,a,b,c \right) =\sum_{0\le i\le n}{\sum_{0\le j\le \lfloor \frac{ai+b}{c} \rfloor -1}{1}} \\ =\sum_{0\le i\le n}{\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\left[ j<\lfloor \frac{ai+b}{c} \rfloor \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ j<\lfloor \frac{ai+b}{c} \rfloor \right]}} \\ \text{由于}\lfloor \frac{ai+b}{c} \rfloor =\lceil \frac{ai+b-c+1}{c} \rceil \\ \left( \begin{array}{c} \text{证明直接考虑:对于}\frac{an+b}{c}\text{为非整数时,}\\ \lfloor \frac{an+b}{c} \rfloor =\lceil \frac{an+b}{c}-1 \rceil =\lceil \frac{an+b-c}{c} \rceil \text{成立,对于整数,加上修正值}\frac{1}{c}\text{即可}\\ \end{array} \right) \\ \text{原式}=\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ j<\lceil \frac{ai+b-c+1}{c} \rceil \right]}} \\ \text{又因为当}a<\lceil \frac{b}{c} \rceil \text{时,有}ac<b \\ \text{原式}=\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ jc<ai+b-c+1 \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ ai>jc-b+c-1 \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\sum_{0\le i\le n}{\left[ i\ge \lfloor \frac{jc-b+c-1}{a} \rfloor \right]}} \\ =\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{n-\sum_{0\le i\le n}{\left[ i<\lfloor \frac{jc-b+c-1}{a} \rfloor \right]}} \\ =n\times \left( \lfloor \frac{an+b}{c} \rfloor \right) -\sum_{0\le j\le \lfloor \frac{an+b}{c} \rfloor -1}{\lfloor \frac{jc-b+c-1}{a} \rfloor} \\ =n\times \left( \lfloor \frac{an+b}{c} \rfloor \right) -f\left( \lfloor \frac{an+b}{c} \rfloor -\text{1,}c,-b+c-\text{1,}a \right) \\ \text{边界条件:} \\ f\left( \text{0,}a,b,c \right) =\lfloor \frac{b}{c} \rfloor \\ f\left( n,a,b,c \right) \left( a\ge c\text{或}b\ge c \right) =\sum_{0\le i\le n}{\lfloor \frac{ai+b}{c} \rfloor} \\ =\sum_{0\le i\le n}{\lfloor \frac{ai}{c}+\frac{b}{c} \rfloor} \\ =\sum_{0\le i\le n}{\lfloor \left( \lfloor \frac{a}{c} \rfloor +\frac{a-c\lfloor \frac{a}{c} \rfloor}{c} \right) i+\lfloor \frac{b}{c} \rfloor +\frac{b-c\lfloor \frac{b}{c} \rfloor}{c} \rfloor} \\ =\sum_{0\le i\le n}{\lfloor \frac{\left( a\,\,\text{mod }c \right) i+b\,\,\text{mod }c}{c} \rfloor +i\lfloor \frac{a}{c} \rfloor +\lfloor \frac{b}{c} \rfloor} \\ =\frac{n\left( n+1 \right)}{2}\lfloor \frac{a}{c} \rfloor +\lfloor \frac{b}{c} \rfloor \left( n+1 \right) +\sum_{0\le i\le n}{\lfloor \frac{\left( a\,\,\text{mod }c \right) i+b\,\,\text{mod }c}{c} \rfloor} \\ =\frac{n\left( n+1 \right)}{2}\lfloor \frac{a}{c} \rfloor +\lfloor \frac{b}{c} \rfloor \left( n+1 \right) +f\left( n,a\,\,\text{mod }c,b\,\,\text{mod }c,c \right) \\ \text{复杂度}O\left( \log N \right) $$

    #include <assert.h>
    #include <algorithm>
    #include <cstdio>
    #include <cstdlib>
    #include <iostream>
    #include <vector>
    
    using int_t = long long int;
    using std::cin;
    using std::cout;
    using std::endl;
    int_t n, m;
    struct Result {
        int_t x, y, pos;
    };
    
    int_t gcd(int_t a, int_t b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    //��ȡб��Ϊy/x��ֱ���������ڵ��������
    int_t getCountOnLine(int_t x, int_t y, int_t n, int_t m) {
        return std::min(n / x, m / y);
    }
    int_t fx(int_t n, int_t a, int_t b, int_t c) {
        if (n < 0) return 0;
        if (n == 0) return b / c;
        if (a >= c || b >= c) {
            return fx(n, a % c, b % c, c) + (n * (n + 1) / 2 * (a / c)) +
                   (n + 1) * (b / c);
        } else {
            if (a == 0)
                return 0;
            else {
                return n * ((a * n + b) / c) -
                       fx((a * n + b) / c - 1, c, c - b - 1, a);
            }
        }
    }
    // x��1��n�ڣ�y��1��m�ڣ�������a/b�ķ�������
    int_t getCount(int_t a, int_t b, int_t n, int_t m) {
        int_t d = (m * a) / b + ((m * a) % b != 0);
        int_t c = std::min(n, d - 1);
        int_t result = c * m - (fx(c, b, 0, a)) + getCountOnLine(a, b, n, m);
        return result;
    }
    Result walk(int_t n, int_t m, int_t k) {
        const auto check = [&](int_t a, int_t b) -> int_t {
            //���Ϸ�
            if (a > n || b > m) return 2;
            int_t under = getCount(a, b, n, m);
            int_t line = getCountOnLine(a, b, n, m);
            // a/b��С
            if (k > under) return -1;
            // a/b����
            else if (k < under - line + 1)
                return 1;
            else
                return 0;
        };
        //��ǰ������Ҳ�ķ���
        int_t leftA = 0, leftB = 1, rightA = 1, rightB = 0;
        int_t A, B;
        while (true) {
            int_t nextA = leftA + rightA;
            int_t nextB = leftB + rightB;
            int_t x = check(nextA, nextB);
            if (x == 0) {
                A = nextA;
                B = nextB;
                break;
            }
            int_t left = 1, right = n;
            int_t result = 0;
            //���ұ�������
            if (x < 0) {
                while (left <= right) {
                    int_t mid = (left + right) / 2;
                    if (check(leftA + mid * rightA, leftB + mid * rightB) < 0) {
                        left = mid + 1;
                        result = mid;
                    } else {
                        right = mid - 1;
                    }
                }
                leftA += result * rightA;
                leftB += result * rightB;
    
            } else {
                //������
                while (left <= right) {
                    int_t mid = (left + right) / 2;
                    if (check(rightA + mid * leftA, rightB + mid * leftB) == 1) {
                        left = mid + 1;
                        result = mid;
                    } else {
                        right = mid - 1;
                    }
                }
                rightA += result * leftA;
                rightB += result * leftB;
            }
        }
        int_t under = getCount(A, B, n, m) - getCountOnLine(A, B, n, m);
        k -= under;
        return Result{A * k, B * k};
    }
    void query(int_t n, int_t m, int_t k) {
        if (k <= m - 1) {
            printf("%lld %lld\n", 1ll, k + 1);
        } else if (k > (n * (m - 1))) {
            printf("%lld %lld\n", k - (n * (m - 1)) + 1, 1ll);
        } else {
            auto result = walk(n - 1, m - 1, k - (m - 1));
            printf("%lld %lld\n", result.x + 1, result.y + 1);
        }
    }
    int main() {
        // while (true) {
        //     int_t a, b, n, m;
        //     cin >> a >> b >> n >> m;
        //     cout << getCount(a, b, n, m) << endl;
        // }
        int T;
        scanf("%d", &T);
        while (T--) {
            int_t n, m, k;
            scanf("%lld%lld%lld", &n, &m, &k);
            query(n, m, k);
        }
    
        return 0;
    }