[HAOI2012]外星人

2749: [HAOI2012]外星人

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 796 Solved: 423
[Submit][Status][Discuss]

Description

Input

Output

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

Sample Input

1
2
2 2
3 1

Sample Output

HINT

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

Source

[分析]：　　

　　对于一个质因数p，等于2直接就消去了，大于2的时候，p-1肯定能被2整除，所以进行求一次欧拉函数之后，直到消完质因数都含有2，而且明显2的个数是最多的，每次还只会消去一个2，所以最后消去的一定是2。

　　那么，问题就变成了询问所有质因数消除的时候会产生多少个2。

　　因为p小于100000，可以预处理一下每个p分解会产生多少个2。

　　回答询问是回答2的个数，需要注意的是，如果一开始的质因数不含有2的话答案为2的个数加一。

//this code is wrong.
#include<cstdio>
using namespace std;
typedef long long ll;
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
const int N=1e5+10;
int m,cas,maxp;
ll contain[N]={0,1};
void prime(){
    maxp=1e5+5;
    for(int i=2;i<=maxp;i++){
        if(contain[i]) continue;
        contain[i]=contain[i-1];
        for(int j=2;i*j<=maxp;j++){
            if(contain[j]) contain[i*j]=contain[i]+contain[j];
        }
    }
}
//contain[p]:p至少phi(p)的次数 
void work(){
    m=read();
    bool flag=0;
    ll sum=0;
    for(int i=1,p,q;i<=m;i++){
        p=read();q=read();
        if(p==2) flag=1;
        sum+=contain[p]*q;//是奇数
    }
    if(flag) printf("%lld
",sum);
    else printf("%lld
",sum+1);
}
int main(){
    prime();
    for(cas=read();cas--;) work();
    return 0;
}