HAOI2012 Alien 外星人

发表于 | 分类于

HAOI2012 外星人 alien

Description

艾利欧在她的被子上发现了一个数字$N$，她觉得只要找出最小的$x$使得$\varphi^x(N)=1$。根据这个$x$她就能找到曾经绑架她的外星人的线索了。当然，她是不会去算，请你帮助她算出最小的$x$。

INPUT

第一行一个正整数$test$,接下来$test$组数据，每组第一行一个正整数$m$，接下来$m$行每行两个正整数$p_i,q_i$。

其中
$$\prod_{i=1}^m p{_i}{^{q_i}}$$
为$N$的标准分解形式。

OUTPUT

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

SAMPLE INPUT

1
2
2 2
3 1

SAMPLE OUTPUT

3

HINT

$N=12,\varphi(12)=4,\varphi(4)=2,\varphi(2)=1$,所以答案是$3$。
$$\varphi(\prod_{i=1}^m p_i^{q_i})$$

$$ =\prod_{i=1}^m (p_i-1) p_i^{q_i-1}$$

$test<=50,p_i<=10^5,1<=q_i<=10^9$

题解

首先打出2~20的$\varphi()$表观察一下。

2 1
3 2
4 2
5 4
6 2
7 6
8 4
9 6
10 4
11 10
12 4
13 12
14 6
15 8
16 8
17 16
18 6
19 18
20 8

可以看得出来，只有$\varphi(2)=1$

而且根据给出的公式很好证明，给定的正整数分解出来的$2$的个数就是答案。
所以线性筛一下，$f[]$数组就代表的是分解出来的$2$的个数

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
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e6+100;
int mark[N],prime[N],cnt,phi[N],tot,nn,n,t,f[N];
void calphi()
{
    f[1]=1;
    for(int i=2;i<=1e6+1;i++)
        {
            if(mark[i]==false)
                prime[cnt++]=i,phi[i]=i-1,f[i]=f[i-1];
            for(int j=0;j<cnt&&i*prime[j]<=1e6+1;j++)
            {
                mark[i*prime[j]]=true;
                f[prime[j]*i]=f[i]+f[prime[j]];
                if(i%prime[j]==0)
                {
                    phi[i*prime[j]]=phi[i]*prime[j];
                    break;
                }
                else
                    phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
}
void bl()   //30'暴力
{
    long long phii=1;
    for(int i=1;i<=n;i++)
    {
        int p,q;
        scanf("%d%d",&p,&q);
        phii*=(p-1);
        for(int i=1;i<q;i++)
            phii*=p;
    }
    long long i=phii;
    while(phi[i]!=1)
    {
        i=phi[i];
        tot++;
    }
    tot++; 
} 
int main()
{
    calphi();
    scanf("%d",&t);
    while(t--)
    {
        tot=1;
        scanf("%d",&n);
        //bl();
        long long yes=1,ans=0;
        for(int i=1;i<=n;i++)
        {
            int p,q;
            scanf("%d%d",&p,&q);
            if(p==2)
                yes=0;
            ans+=(long long)f[p]*q;
        }
        printf("%lld\n",yes+ans);
    }
}