数论·欧拉函数·[HAOI2012]外星人

[HAOI2012]外星人

题目大意：给定一个数N，问你这个数取多少次欧拉函数后变成1
题目类型：欧拉函数

Input
test（数据数量），每组一个m，接下来m个pi，qi，为n的标准分解形式

Output

输出test行整数

Sample Input

1 2
2 2
3 1

Sample Output

3

题解

注意到只有phi[2]=1，所以每个数最终都是要经过phi[2]=1这一步变为1

而每一次做欧拉函数，根据欧拉函数的计算式可以看出：会产生一个2，也必会消掉一个2. 每个pi做一次欧拉函数，就变成了pi-1，而pi减1必为合数，除非pi为2，pi-1又分解为若干个pi的qi次方，继续下去，直到pi为2，结束，则有多少个2，就需要多少次。 因此我们只需要算出原数N的质因子一共会产生多少个2即可 于是我们令f[i]表示i分解出了几个2： i为质数，f[i] = f[i - 1]；否则，f[i * prime[j] = f[i] + f[prime[j]]
另：如果一开始n为奇数，则ans需+ 1，因为变出2需要第一步。 因为若开始是奇数，第一次做欧拉函数是不会消掉2的，且运作到中间不会出现没有2的情况，因为pi为奇数，pi-1则必定为偶数，2一定会有的。

代码

    #include<bits/stdc++.h>typedef long long ll;using namespace std;const ll M = 1e5+10;ll f[M], prime[M/2],cnt = 0,test;bool check[M];void make_prime(){
    f[1] = 1;for(ll i = 2; i <= M; i++){
    if(!check[i]) prime[++cnt] = i,f[i] = f[i - 1];for(ll j = 1; j <= cnt && i * prime[j] <= M; j++){
    check[i * prime[j]] = 1;f[i * prime[j]] = f[i] + f[prime[j]];if(i%prime[j] == 0) break;}}}int main(){
    // freopen("alien.in","r",stdin);// freopen("alien.out","w",stdout);scanf("%lld",&test);make_prime();while(test--){
    ll ans = 1,m,pi,qi;scanf("%lld",&m);for(ll i = 1; i <= m;i++){
    scanf("%lld%lld",&pi,&qi);if(pi == 2) ans--;ans += f[pi] * qi;}printf("%lld\n",ans);}return 0;}