记录编号	274667	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]外星人	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.551 s
提交时间	2016-06-29 10:59:52	内存使用	2.41 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;

const int N=100010;
int p[N],cnt;
unsigned long long c[N],ans;
bool hash[1000010];
int find(int x,int l,int r){
	if (l==r) return l;
	int m=(l+r)/2;
	return p[m+1]>x?find(x,l,m):find(x,m+1,r);
}
inline void fenjie(int x){
	int i=1,y=p[x]-1;
	for (;p[i]<=sqrt(y);i++)
		while (y%p[i]==0) y/=p[i],c[x]+=c[i];
	if (y!=1) c[x]+=c[find(y,1,x)];
}
void prework(){
	for (int i=2;i<=1000000;i++)
	if (!hash[i]){
		p[++cnt]=i;
		for (int j=i+i;j<=1000000;j+=i) hash[j]=1;
	}
	c[1]=1;
	for (int i=2;i<=cnt;i++) fenjie(i);
}

int main()
{
	freopen("alien.in","r",stdin);
	freopen("alien.out","w",stdout);
	prework();
	int test,n,p,q;
	scanf("%d",&test);
	while (test--){
		scanf("%d",&n);
		ans=1;
		for (int i=1;i<=n;i++){
			scanf("%d%d",&p,&q);
			if (p==2) ans--;
			ans+=c[find(p,1,cnt)]*q;
		}
		cout<<ans<<endl;
	}
	return 0;
}