Soldier and Number Game CodeForces - 546D

本文主要是介绍Soldier and Number Game CodeForces - 546D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接

给一个数(a!/b!) 每次除一个数 问最多能除多少次

很容易想到算数基本定理 n=(p1^a1)*(p1^ak)*......*(pk^ak) 其中pi是n的素因子 而ai是对应幂次 素因子已经无法再继续分下去 所以按照这个公式来一步一步分解n是次数最多的

先要找出这些素因子 既然是素数那就素数筛预处理 同时如果筛到素因子 就看它的倍数是它的几次幂 这样在筛素数时就把每一个数算数基本定理中的所有ai之和求出来了 因为题目是两个阶乘相除 所以再搞一个前缀和 每次O(1)查询

#include<bits/stdc++.h>
using namespace std;int prime[5000010],pre[5000010];void init()
{int i,j,t;for(i=2;i<=5000000;i++){if(!prime[i]){for(j=i;j<=5000000;j+=i){prime[j]=1;t=j;while(t%i==0){pre[j]++;t/=i;}}}}for(i=1;i<=5000000;i++){pre[i]+=pre[i-1];}return;
}int main()
{int t,a,b;init();scanf("%d",&t);while(t--){scanf("%d%d",&a,&b);printf("%d\n",pre[a]-pre[b]);}return 0;
}

 

这篇关于Soldier and Number Game CodeForces - 546D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---