记录编号	239165	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]外星人	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2016-03-19 23:27:16	内存使用	1.21 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define LL long long
int prime[10010],phi[MAXN+10],tot,f[MAXN+10];
bool vis[MAXN+10];
int read()
{
    int s=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*fh;
}
void getEular()
{
    int i,j;
    phi[1]=1;tot=0;
    for(i=2;i<=MAXN;i++)
    {
        if(vis[i]==false)
        {
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(j=1;j<=tot&&prime[j]*i<=MAXN;j++)
        {
            vis[prime[j]*i]=true;
            if(i%prime[j]==0)
            {
                phi[prime[j]*i]=prime[j]*phi[i];
                break;
            }
            phi[prime[j]*i]=phi[prime[j]]*phi[i];
        }
    }
}
int main()
{
    freopen("alien.in","r",stdin);
    freopen("alien.out","w",stdout);
    int T,i,m,p,q,n;
    bool flag;
    LL ans;
    T=read();
    getEular();
    memset(f,0,sizeof(f));//f[i]代表i需要phi多少次才能化为1.(也就是等于能phi多少个2.)
    f[1]=-1;
    for(i=2;i<=MAXN;i++)f[i]=f[phi[i]]+1;
    f[1]++;f[2]++;
    while(T--)
    {
        m=read();ans=0;
        flag=false;//判断奇数时要加一.
        for(i=1;i<=m;i++)
        {
            p=read();q=read();
            if(p==2)flag=true;
            ans+=(LL)f[p]*q;
        }
        if(flag==false)ans++;
        printf("%lld\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}