BZOJ 2749 - [HAOI2012]外星人

#数学 #数论 #线性筛
Published on 2017-01-20

题目地址

描述

设 f(n)f(n) 为最少经过几次 n=φ(n)n = \varphi(n) 的变换使得 n=1n = 1。给定 nn 的标准分解形式：

n=∏1≤i≤mpiqi n = \prod_{1\le i\le m} p_i^{q_i}

其中 pi≤105,1≤qi≤109p_i\le {10}^5, 1\le q_i \le {10}^9。请你求 f(n)f(n)。

分析

拿到这题我们可以发现，暴力算是不行的，nn 会极大，而且 f(n)f(n) 显然不具有积性之类的性质，我们要寻找一些性质来帮助解题。

我们考虑 φ\varphi 的性质，首先是展开形式：

φ(∏i=1mpiki)=∏i=1m(pi−1)piki−1 \varphi(\prod_{i = 1}^m p_i^{k_i}) = \prod_{i = 1}^m (p_i - 1)p_i^{k_i - 1}

以及 n≥3n\ge 3 时，满足 φ(n)\varphi(n) 为偶数，这是因为 gcd(n,x)=gcd(n,n−x)\gcd(n, x) = \gcd(n, n - x)，所以互质的数必然是成对出现。

当 n≥2n \ge 2 时，由于只有 φ(2)=1\varphi(2) = 1，所以 nn 必然要先变换到 22，然后才能变换到 11。假设 nn 是偶数，那么经过一次变换，所有质因子的指数会减少 11，取而代之的是 (p1−1)(p2−1)⋯(pm−1)(p_1 - 1)(p_2 - 1)\cdots(p_m - 1)（这些都是偶数）。也就是说，这一次变换会去掉质因子 22 的一个指数，同时生成至少一个质因子 22（只要 nn 不是 2x2^x 的形式），那就是说，每次变换至少有一个 22 可以去掉，所以经过若干次变换，一定会变换到 n=2x,x≥0n = 2^x, x \ge 0 的形式，此时还需要 xx 步才能变到 11。也就是说，我们在变换能生成多少个 22，我们就需要多少步来达到 11。

对于奇数，假设能生成 xx 个 22，需要 x+1x + 1 步才能变换到 11，原因是需要一步来生成一个 22。

设 g(n)g(n) 为 nn 经过若干次 n=φ(n)n = \varphi(n) 的变换中，会生成多少个 22，不难发现，g(n)g(n) 满足：

这样就可以使用线性筛法筛出 g(n)g(n)，回答询问的时候，需要用到 g(pk)=k⋅g(p)g(p^k) = k\cdot g(p)，同时需要有判断有无 22 这个质因子来确定奇偶性。

代码

//  Created by Sengxian on 2017/01/20.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 2749 数论
#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 * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3;

int primes[MAX_N], f[MAX_N], cnt = 0;
bool isPrime[MAX_N];

void prepare() {
    fill(isPrime + 2, isPrime + MAX_N, true);
    f[2] = 1;
    for (int i = 2; i < MAX_N; ++i) {
        if (isPrime[i]) primes[cnt++] = i, f[i] = i == 2 ? 1 : f[i - 1];
        for (int j = 0; j < cnt && i * primes[j] < MAX_N; ++j) {
            int t = i * primes[j];
            isPrime[t] = false;
            f[t] = f[i] + f[primes[j]];
            if (i % primes[j] == 0)    break;
        }
    }
}

int main() {
    prepare();

    int caseNum = readInt();
    while (caseNum--) {
        int n = readInt();
        ll ans = 0;
        bool flag = false;
        while (n--) {
            int p = readInt(), k = readInt();
            flag |= p == 2;
            ans += (ll)f[p] * k;
        }

        printf("%lld\n", ans + (!flag));
    }
    return 0;
}
BZOJ 4377 - [POI2015]Kurs szybkiego czytania