BZOJ2749 HAOI2012外星人（数论）

　　不妨把求φ抽象成把将每个位置上的一个小球左移一格并分裂的过程，那么即求所有球都被移到1号格子的步数。

　　显然要达到1必须先到达2。可以发现每次分裂一定会分裂出2号位的球，因为2以外的质数一定是奇数。以及，每次移动至多将一个2号位的球移至1号位。

　　于是我们只要数出每个位置能将几个球分裂至2号位就可以了。注意初始时若2号位没有球答案要+1。

　　这个数数可以用线性筛搞定。n为质数则有f[n]=f[n-1]，否则有f[n]=f[prime]+f[n/prime]。

　　（挤进bzoj前1k了www

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

int T,n,f[N],prime[N],cnt=;

bool flag[N];

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    flag[]=;f[]=;

    for (int i=;i<=N-;i++)

    {

        if (!flag[i]) prime[++cnt]=i,f[i]=f[i-];

        for (int j=;j<=cnt&&prime[j]*i<=N-;j++)

        {

            flag[prime[j]*i]=;

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

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

        }

    }

    T=read();

    while (T--)

    {

        n=read();

        long long ans=;

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

        {

            int x=read(),y=read();

            ans+=1ll*y*f[x]-(x==);

        }

        printf(LL,ans);

    }

    return ;

}

巴特西

BZOJ2749 HAOI2012外星人（数论）

最新文章

热门文章