【bzoj2749】[HAOI2012]外星人

2749: [HAOI2012]外星人

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 677  Solved: 360
[Submit][Status][Discuss]

Description

Input

Output

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

Sample Input

1
2
2 2
3 1

Sample Output

3

 

 

 

【题解】

 

注意到只有phi[2]=1，所以每个数最终都是要经过phi[2]=1这一步变为1

 

而每一次做欧拉函数，从这个式子可以看出：会产生一个2，也必会消掉一个2

 

因此我们只需要算出原数N的质因子一共会产生多少个2即可

 

于是我们令f[i]表示i分解出了几个2：这一过程类似素数筛法

 

i为质数，f[i] = f[i - 1]；否则，f[i * prime[j] = f[i] + f[prime[j]]  （<--这就是传说中的纯O(n)线性筛）

 

另：如果一开始n为奇数，则ans需+ 1，因为变出2需要第一步。

 

 /*************

   bzoj 2749

   by chty

   2016.11.4

 *************/

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define MAXN 100000

 typedef long long ll;

 ll T,n,cnt,check[MAXN+],prime[MAXN+],f[MAXN+];

 inline ll read()

 {

     ll x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 void pre()

 {

     f[]=;

     for(ll i=;i<=MAXN;i++)

     {

         if(!check[i])  {prime[++cnt]=i;  f[i]=f[i-];}

         for(ll j=;j<=cnt&&prime[j]*i<=MAXN;j++)

         {

             check[prime[j]*i]=;

             f[prime[j]*i]=f[prime[j]]+f[i];

             if(i%prime[j]==)  break;

         }

     }

 }

 int main()

 {

     freopen("cin.in","r",stdin);

     freopen("cout.out","w",stdout);

     T=read();  pre();

     while(T--)

     {

         n=read();  ll ans();

         for(ll i=;i<=n;i++)

         {

             ll p=read(),q=read();

             if(p==)  ans--;

             ans+=f[p]*q;

         }

         printf("%lld\n",ans);

     }

     return ;

 }