题意（Codeforces 546D）

给定一个数x=a!b!" role="presentation">x=a!b!x=a!b!的形式，问其中有几个质因数。

分析

数据规模略大，故先作预处理。预处理的时候运用了前缀和和记忆化搜索的思想。

之后就比较简单了。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll = long long;

using ull = unsigned long long;

using pi = pair<int,int>;

const int MAXN=5000000;

bool isPrime[MAXN+5];

ll cnt[MAXN+5];

ll getCnt(int x)

{

    if(cnt[x]!=-1) return cnt[x];

    else

    {

        if(isPrime[x]) return cnt[x]=1;

        for(int i=2;i*i<=x;++i)

        {

            if(isPrime[i] && x%i==0) return cnt[x]=getCnt(x/i)+1;

        }

    }

}

ll sum[MAXN+5];

int main()

{

QUICKIO

    memset(isPrime,true,sizeof(isPrime));

    ZERO(sum);

    isPrime[0]=isPrime[1]=false;

    rep(i,2,MAXN)

    {

        if(isPrime[i])

        {

            for(int j=i*2;j<=MAXN;j+=i)

                isPrime[j]=false;

        }

    }

    memset(cnt,-1,sizeof(cnt));

    cnt[1]=0;

    rep(i,1,MAXN)

    {

        sum[i]=sum[i-1]+getCnt(i);

        //cout<<sum[i]<<endl;

    }

    //rep(i,1,100) cout<<sum[i]<<" "; cout<<endl;

    int t;

    scanf("%d",&t);

    rep(i,1,t)

    {

        int a,b;

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

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

        //cout<<" "<<a<<" "<<sum[a]<<" "<<b<<" "<<sum[b]<<endl;

    }

    //rep(i,1,100) cout<<sum[i]<<" "; cout<<endl;

    return 0;

}

巴特西

「日常训练」 Soldier and Number Game (CFR304D2D)

题意（Codeforces 546D）

分析

代码

最新文章

热门文章

巴特西

「日常训练」 Soldier and Number Game (CFR304D2D)

题意 （Codeforces 546D）

分析

代码

最新文章

热门文章

题意（Codeforces 546D）