[Solution][数论]BZOJ2749

【题目】

戳这里

【思路】

Hint里面的转化式非常重要,是我们解决此题思路的来源。

定义一次操作为.

对于每一个奇质数,每一次操作相当于使的次数减1,同时把分解质因数,把得到的质因数次数增加。但是对于偶质数2,每一次操作其次数必定减1.

当原来所有的质因数次数均为0时,操作完成。

注意到不同的质数之间是互不影响的,我们任取一个奇质数,对其进行操作,不过这次每次操作时不把2的次数减1,那么我们发现,最终得到的必然是2的若干次幂。

对于一个给定质数,最终对其进行不减少2的次数操作,最终得到的2的次数显然是定值。

我们可以用欧拉线性筛进行预处理:定义.

注意到每次操作2的次数必定减少1,因而总的操作次数就是所有质数能够转化出来的2的总个数。

特别地,当原数N不存在质因子2时,答案加1,因为第一次操作时没有2可以消去。

【代码】

#include<cstdio>
#include<cstring>
#define N (100000)
typedef long long LL;
int prime[N + 10] , top , get[N + 10];
bool notprime[N + 10];
int main()
{
    register int i , j , k;
    get[1] = 1;
    for(i = 2 ; i <= N ; ++i)
    {
        if (!notprime[i])
        {
            prime[++top] = i;
            get[i] = get[i - 1];
        }
        for(j = 1 ; j <= top ; ++j)
        {
            if (i * prime[j] > N)
                break;
            notprime[i * prime[j]] = 1;
            get[i * prime[j]] = get[i] + get[prime[j]];
            if (i % prime[j] == 0)
                break;
        }
    }
    int T;
    scanf("%d" , &T);
    while(T--)
    {
        LL res = 0;
        int n;
        scanf("%d" , &n);
        bool isodd = 1;
        int p , q;
        for(i = 1 ; i <= n ; ++i)
        {
            scanf("%d%d" , &p , &q);
            if (!(p & 1))
                isodd = 0;
            res += (LL)get[p] * q;
        }
        res += isodd;
        printf("%lld\n" , res);
    }
    return 0;
}
comments powered by Disqus