外星人

Time Limit: 3 Sec Memory Limit: 128 MB

Description

img

Input

img

Output

输出test行，每行一个整数，表示答案。

Sample Input

1
　2
　2 2
　3 1

Sample Output

3

img

HINT

Test<=50 Pi<=10^5,1<=Q1<=10^9

Main idea

给定一个数，用Πp[i]^qi的形式表示，问最少需要对这个数字x进行几次x=Φ(x)操作使得x=1。

Solution

这显然是一道数论题。
　　首先想到了只有Φ(2)=1，所以最后答案必然需要转成带2的形式，我们先考虑一个数字，由欧拉函数的推导公式Φ(Πp[i]^q[i])=Π(p[i]-1)*p[i]^(q[i]-1)可以发现每次求Φ会消去一个质因数2，并且产生若干个2（产生的2是有上限的）。
　　这句话是什么意思呢？
　　我们举个例子：讨论一个偶数180=2^2 * 3^2 * 5，Φ(180)=2^1 * (3-1)*3 * (5-1)=48，这里产生了3个2，消去了1个2。
　　所以我们只要求出产生了几个2即可（由于除了Φ(2)以外的数都是偶数，所以任意奇数只要经过一遍求Φ就可以变为偶数来处理，次数+1），因为每次只能消去一个1，所以答案就应该是这个数分解出的2的个数。
　　知道欧拉函数是一个积性函数，并且我们现在求的显然是一个完全积性函数，由于这个性质，求分解出几个2可以使用线性筛来实现，对于每一项p[i]^q[i]分解出的个数就是(p[i]分解出的个数*q[i])，答案就是Σ(每一项分解出的个数)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

const int ONE=100001;

int T;
int f[ONE],p[ONE],tot,phi[ONE];
int x,y,m,PD;
long long Ans;

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Get_f(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!f[i])
        {
            p[++tot]=i;
            phi[i]=phi[i-1];
        }

        for(int j=1;j<=tot;j++)
        {
            if(i*p[j]>n) break;
            f[i*p[j]]=1;
            phi[i*p[j]]=phi[i]+phi[p[j]];
            if(i%p[j]==0) break;
        }
    }
}

int main()
{
    Get_f(ONE-1);
    T=get();
    while(T--)
    {
        m=get();
        Ans=PD=0;
        for(int i=1;i<=m;i++)
        {
            x=get();    y=get();
            Ans+=(long long)phi[x]*y;
            if(!PD && x==2) PD=1;
        }
        printf("%lld\n",Ans+(!PD));
    }
}