Description

题目链接

题目大意:求最小的 $x$,满足 $\varphi^x(n) = 1$。

Solution

其实是问 $\varphi(n)$ 经过多少次迭代等于 $1$。

首先可以知道只有 $\varphi(1)$ 和 $\varphi(2)$ 等于 $1$。

接下来根据欧拉函数的性质:

$$ \varphi(\prod p_i ^ {q_i}) = \prod (p_i - 1) \times p_i^{q_i - 1} $$

每次迭代会使每个质因数减一,其实只需要求每个质因数能产生几个 $2$。

设 $f(i)$ 表示 $i$ 能产生几个 $2$,当 $i$ 是质数时,$f(i) = f(i - 1)$,否则 $f(ab) = f(a) + f(b)$。

显然可以线性筛。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <set>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef long long LL;
typedef unsigned long long uLL;

std::vector<int> p;
int f[100010];
int T, m, ans;
bool isPrime[100010];

int main() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    f[1] = 1;
    for (int i = 2; i <= 1e5; ++i) {
        if (isPrime[i]) {
            p.push_back(i);
            f[i] = f[i - 1];
        }
        for (auto j : p) {
            if (i * j > 1e5)    break;
            isPrime[i * j] = false;
            f[i * j] = f[i] + f[j];
            if (i % j == 0)    break;
        }
    }
    read(T);
    while (T--) {
        read(m);
        ans = 1;
        for (int i = 1, p, q; i <= m; ++i) {
            read(p), read(q);
            if (p == 2)    --ans;
            ans += f[p] * q;
        }
        printf("%d\n", ans);
    }
    return 0;
}
Last modification:November 19th, 2021 at 06:28 pm