题解：P2350 [HAOI2012] 外星人

· · 题解

视频讲解：https://www.bilibili.com/video/BV1ZT2iBjEe7/?spm_id_from=333.1391.0.0&vd_source=535beb5cfca15a72bb67737f5411dc81

直接暴力求数值太大、不可取，需要巧借欧拉函数性质。

本题要用到的欧拉函数性质有：

1.设 p 是质数，𝜑(pk) = pk-pk-1 = (p-1)*pk-1

2.欧拉函数是积性函数：n，m互质则𝜑(n*m) = 𝜑(n)*𝜑(m)

题目是想让我们嵌套ans次后得到1，显然φ(2)=1，我们应当努力向φ(2)靠拢。

首先容易想到： 质因子是2时，N=2n 时答案是 n (需要消去n层括号)： 如N=2^3 时，φ(((8))) 那么，ans=3
即φ(2^3)=2^2 -> φ(2^2)=2 -> φ(2^1)=1

质因子是其他奇素数时，根据性质1、2或题面提示得： 每一次消去一层括号都相当于消去一次2(只要有2)，并且产生许多个2(只要有奇数)。 如N=5^3时，φ(5^3)=4*5^2 -> φ(2^2*5^2)=(2)*(4*5^1) -> φ(2^3*5^1)=...

也就是说：我们只需要求出转化过程中一共能产生多少个2就是答案了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
bool ispri[N]; // 判质数 
int pri[N], cnt; // 存质数 
int num[N]; // i能转化成几个2 

void euler() { // 筛法求i能转化成几个2
    memset(ispri, true, sizeof ispri);
    ispri[0]=ispri[1]=false;
    num[1]=1;
    for(int i=2; i < N; i++) {
        if(ispri[i]) pri[++cnt]=i, num[i]=num[i-1];
        for(int j=1; 1LL*i*pri[j] < N; j++) {
            ispri[i*pri[j]]=false;
            if(i%pri[j] == 0) {
                num[i*pri[j]]=num[i]+num[pri[j]];
                break;
            }
            else num[i*pri[j]]=num[i]+num[pri[j]];
        }
    }
}

signed main() {
    euler(); 
    int t;
    cin >> t;
    while(t--) {
        int n, ans=0;
        cin >> n;
        for(int i=1, p, q; i <= n; i++) {
            cin >> p >> q;
            if(p == 2) ans--; 
            ans+=num[p]*q;
        }
        cout << ans+1 << '\n';
    } 
    return 0;
}