记录编号	155252	评测结果	AAAAAAAAAA
题目名称	792.[HAOI 2012]外星人	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.088 s
提交时间	2015-03-27 23:29:55	内存使用	1.91 MiB

/***********************************************************************/ 
/**********************By Asm.Def-Wu Jiaxin*****************************/ 
/***********************************************************************/ 
#include <cstdio>
#include <cctype>
using namespace std; 
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) ) 
#define getc() getchar() 
template<class T>inline void getd(T &x){ 
	char ch = getc();
	bool neg = false; 
	while(!isdigit(ch) && ch != '-')ch = getc(); 
	if(ch == '-')ch = getc(), neg = true; 
	x = ch - '0'; 
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch; 
	if(neg)x = -x; 
} 
/***********************************************************************/ 
const int maxp = 100003; 
int Prime[maxp], pcnt = 0, dp[maxp] = {0}, Phi[maxp], cnt[maxp], pow2[18]; 
bool not_p[maxp]; 
inline void sieve(){ 
	int i, j; 
	for(i = 2;i <= 100000;++i){ 
		if(!not_p[i])Prime[pcnt++] = i, Phi[i] = i-1; 
		for(j = 0;j < pcnt;++j){ 
			if(i * Prime[j] > 100000)break; 
			not_p[i * Prime[j]] = true; 
			if(i % Prime[j] == 0){ 
				Phi[i * Prime[j]] = Prime[j] * Phi[i]; 
				break; 
			} 
			Phi[i * Prime[j]] = Phi[i] * (Prime[j]-1); 
		} 
	} 
} 
inline void init(){ 
	sieve(); 
	int i, j, t = 1;
	for(i = 1;i <= 18;++i){
		t <<= 1; 
		for(j = t;j <= 100000;j += t)++cnt[j]; 
	} 
	for(i = 3;i <= 100000;++i)
		cnt[i] += cnt[Phi[i >> cnt[i]]]; 
} 
inline void work(){ 
	int m, i, p, a;
	getd(m); 
	long long ans; 
	getd(p), getd(a); 
	ans = (long long)a * cnt[p] + (p != 2); 
	for(i = 1;i < m;++i){ 
		getd(p), getd(a); 
		ans += (long long)a * cnt[p]; 
	} 
	printf("%lld\n", ans); 
} 
int main(){ 
#ifdef DEBUG 
	freopen("test.txt", "r", stdin); 
#elif !defined ONLINE_JUDGE 
	SetFile(alien); 
#endif 
	init();
	int T;getd(T); 
	while(T--) work(); 
#ifdef DEBUG 
	printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC); 
#endif 
	return 0; 
}