【题解】BZOJ 2749 [HAOI2012]外星人

Problem

给定正整数 $m$ ,求最小的 $x$ 使得 $\phi^x(m)=1$
其中 $m$ 以其标准分解方式给出

Thought

考虑 $\phi$ 的性质: $\phi(\prod p_i^{q_i})=\prod (p_i-1)p_i^{q_i-1}$
将每次变换后的 $(p_i-1)$ 同样的化为质数积的形式,发现每个数在变为 $1$ 之前,必然变为 $2$

并且,每次求 $\phi$ 会且仅会消耗一个 $2$ ,而可能会增加若干个 $2$ (除 $2$ 之外当前有多少个不同的质数就会增加多少个 $2$)

那么,我们就可以用 $2$ 的总数来描述需要进行求 $\phi$ 的次数

设 $g(x)$ 表示在对其多次求 $\phi$ 的过程中会生成多少个 $2$ ,显然有:

$$ g(1)=0,g(2)=1\\ g(p)=g(p-1)\\ g(ab)=g(a)+g(b)\\ $$

然后线性筛就完事了

注意:如果在刚开始时没有 $2$ 这个质因数,答案为 $num+1$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
bool no[100010];
int pri[100010], priCnt;
int g[100010];
ll m;

namespace math {
    ll mod;
    ll M(ll x) {
        if(x < 0) x += mod;
        if(x >= mod) x -= mod;
        return x;
    }
    ll read(int mod) {
        ll ans = 0, flag = 1;
        char ch = getchar();
        while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
        while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar(); if(mod) ans %= mod;}
        if(mod) return M(ans * flag);
        return ans * flag;
    }
    ll exgcd(ll a, ll b, ll &x , ll &y) {
        if(!b) {x = 1; y = 0; return a;}
        ll gcd = exgcd(b, a % b, x, y);
        ll t = x; x = y; y = t - a / b * y;
        return gcd;
    }
    ll gcd(ll a, ll b) {
        if(!b) return a;
        return gcd(b, a % b);
    }
    void getPri(int N) {
        g[1] = 0;
        for(int i = 2; i < N; ++ i) {
            if(!no[i]) {
                pri[++ priCnt] = i;
                if(i == 2) g[i] = 1;
                else g[i] = g[i - 1];
            }
            for(int j = 1; j <= priCnt && i * pri[j] < N; ++ j) {
                no[i * pri[j]] = 1;
                g[i * pri[j]] = g[i] + g[pri[j]];
                if(i % pri[j] == 0) break;
            }
        }
    }
}
void work() {
    m = read();
    ll ans = 1;
    while(m --) {
        ll p = read(), q = read();
        ans += q * g[p];
        if(p == 2) ans -= 1;
    }
    printf("%lld\n", ans);
}
int main() {
    math :: getPri(100010);
    int t = read();
    while(t --)
        work();
    return 0;
}
Comments

添加新评论