BZOJ 1128 - [POI2008]Lam | Sengxian's Blog

BZOJ 1128 - [POI2008]Lam

#数学 #容斥原理 #高精度

Published on 2016-09-24

描述

对于一个长度为 $n(n\le 1000)$ 的数列 $p(p_i\le {10}^9)$ ，数列中任意两个数互质。准备一个无限长的储存器。然后从 $p_1$ 开始，把储存器中 $p_1$ 倍数位置都赋值为 $p_1$ ，把储存器中 $p_2$ 倍数位置都赋值为 $p_2$ ...最后把储存器中 $p_n$ 倍数位置都赋值为 $p_n$ 。最后求每个 $p_i$ 在储存器中出现的比例，用分数表示。

分析

设所有数的最小公倍数。不难发现，我们只需要考虑储存器的长度为 $\mathrm{lcm}$ 的情况，因为储存器以 $\mathrm{lcm}$ 为周期循环。

我们只需要计算出 $p_i$ 在储存器中的出现次数就行了，由于后面的数可以覆盖前面的数，所以我们考虑倒序计算，然后容斥地计算被覆盖的位置。

不妨设后面的部分为，则有：

\mathrm{ans}_i = \frac {f_{i + 1}} {p_i}

显然 $f_i$ 可以递推计算，边界为 $f_{n + 1} = 1$ ，我们考虑从 $f_{i + 1}$ 转移过来，那么分为选或者不选 $i$ 两种情况

f_i = f_{i + 1} - \frac {f_{i + 1}} {p_i} = f_{i + 1}\cdot\frac {p_i - 1} {p_i}

需要使用高精度 + 分数来处理 $f_i$ ，我们将 $f_i$ 表示为分子分母的最简形式 $\frac x y$ ，那么每次递推的过程中，需要乘上 $\frac {p_i - 1} {p_i}$ ，意味着需要一个高精度数和一个低精度数约分，只需计算出高精度数和低精度数的 $\gcd$ 就行了，而计算 $\gcd$ 需要高精度数对低精度数取模，这个可以用模的定义来求解，利用 $a\bmod b = a - \lfloor a / b\rfloor * b$ 即可搞定。

而高精度与低精度数除法下取整与普通的高精度除低精度并没有区别，所以取模的时间和其余高精度操作计算时间一样，都是 $O(n)$ 的（如果高精度压 $9$ 位，那么位数就是 $O(n)$ 的），总复杂度： $O(n^2)$ 。

代码

//  Created by Sengxian on 09/23/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1128 高精度
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000 + 3;
int n, p[MAX_N];

struct BigInt {
    static const ll BASE = 1000000000LL;
    static const int MAX_DIGIT = MAX_N;
    int len;
    ll digits[MAX_DIGIT];
    BigInt(int v = 0): len(1) {memset(digits, 0, sizeof digits); digits[0] = v;}
    inline BigInt& operator = (const int &v) {
        memset(digits, 0, sizeof digits);
        len = 1, digits[0] = v;
        return *this;
    }
    inline void maintain() {
        len = MAX_DIGIT;
        while (len - 1 >= 1 && digits[len - 1] == 0) len--;
    }
    inline friend BigInt& operator *= (BigInt &lhs, const int &rhs) {
        ll up = 0;
        for (int i = 0; i < lhs.len; ++i) lhs.digits[i] *= rhs;
        for (int i = 0; i < lhs.len || up; ++i) {
            lhs.digits[i] += up;
            up = lhs.digits[i] / BASE;
            lhs.digits[i] %= BASE;
        }
        lhs.maintain();
        return lhs;
    }
    inline friend BigInt operator - (const BigInt &lhs, const BigInt &rhs) {
        int len = max(lhs.len, rhs.len);
        BigInt res(0);
        for (int i = 0; i < len; ++i) {
            res.digits[i] = lhs.digits[i] - rhs.digits[i];
            if (res.digits[i] < 0) res.digits[i] += BASE, res.digits[i + 1]--;
        }
        res.maintain();
        return res;
    }
    inline friend BigInt& operator /= (BigInt &lhs, const int &rhs) {
        ll r = 0;
        for (int i = lhs.len - 1; i >= 0; --i) {
            lhs.digits[i] += r * BASE;
            r = lhs.digits[i] % rhs;
            lhs.digits[i] /= rhs;
        }
        lhs.maintain();
        return lhs;
    }
    inline friend int operator % (const BigInt &lhs, const int &rhs) {
        BigInt tmp = lhs;
        tmp /= rhs;
        tmp *= rhs;
        tmp = lhs - tmp;
        return tmp.digits[0];
    }
    inline void print() {
        if (len == 0) printf("0");
        else {
            printf("%lld", digits[len - 1]);
            for (int i = len - 2; i >= 0; --i)
                printf("%0*lld", 9, digits[i]);
        }
    }
    inline void printLine() {
        print();
        putchar('\n');
    }
};

BigInt f[MAX_N][2];

int main() {
    n = ReadInt();
    BigInt P = 1;
    for (int i = 0; i < n; ++i) P *= p[i] = ReadInt();
    f[n][0] = 1, f[n][1] = 1;
    for (int i = n - 1; i; --i) {
        f[i][0] = f[i + 1][0], f[i][1] = f[i + 1][1];
        int g = __gcd(f[i][0] % p[i], p[i]);
        f[i][0] /= g;
        f[i][1] *= p[i] / g;

        if (p[i] != 1) {    
            g = __gcd(f[i][1] % (p[i] - 1), p[i] - 1);
            f[i][0] *= (p[i] - 1) / g;
            f[i][1] /= g;
        } else f[i][0] = BigInt(0), f[i][1] = BigInt(1);
    }    
    for (int i = 0; i < n; ++i) {
        int g = __gcd(f[i + 1][0] % p[i], p[i]);
        f[i + 1][0] /= g;
        f[i + 1][1] *= p[i] / g;
        (f[i + 1][0]).print();
        putchar('/');
        (f[i + 1][1]).printLine();
    }
    return 0;
}

BZOJ 1129 - [POI2008]Per BZOJ 1122 - [POI2008]账本BBB