Soldier and Number Game---cf546D（打表求n的素因子个数）

题目链接：http://codeforces.com/problemset/problem/546/D

题意：

给出一个n，n开始是a!/b!，每次用一个x去整除n得到新的n，最后当n变成1的时候经过了几轮得分就是这个轮数，要求最大的分数是多少

思路：

很明显，就是一个求整数质因子个数的题目，阶乘我们不需要算，我们知道在a>b的时候，b!都约掉了，那么我们只需压迫计算出每个数的质因数有几个，然后计算出1~n的质因子之和，那么就可以迅速得到答案了

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define N 5000005

using namespace std;

typedef long long LL;

int sum[N], f[N];///f[i]代表i的素数因子有多少个；

void make()

{

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

    {

        if(!f[i])///当i是素数时；那么i的倍数都含有i这个素因子；所以到f[j]=f[j/i]+1;

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

        {

            f[j] = f[j/i] + ;

        }

    }

    for(int i=; i<N; i++)///sum[i]表示1--i以内的每个数的因子总和；

        sum[i]=sum[i-]+f[i];

}

int main()

{

    make();

    int T, a, b;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d %d", &a, &b);

        printf("%d\n", sum[a]-sum[b]);

    }

    return ;

}

巴特西

Soldier and Number Game---cf546D（打表求n的素因子个数）

最新文章

热门文章