SPOJ:Divisors of factorial (hard) (唯一分解&分块优化)
Factorial numbers are getting big very soon, you'll have to compute the number of divisors of such highly composite numbers.
Input
The first line contains an integer T, the number of test cases.
On the next T lines, you will be given two integers N and M.
Output
Output T lines, one for each test case, with the number of divisors of the factorial of N.
Since the answer can get very big, output it modulo M.
Example
Input:
3
2 1000
3 11
4 5
Output:
2
4
3
Constraints
0 < T < 5432
1 < N < 10^8
1 < M < 10^9
For N, M : uniform random input in the range.
One input file.
题意: T组数据 给定N,M ; 求N的阶乘的因子个数 , 结果模M .
思路: 对于求某个数的因子个数 , 我们知道是唯一分解为素数 ,表示为素数的幂的乘积形式a1^p1*a2^p2... 然后结果就是所有(p1+1)*(p2+1)...的乘积.
但是这里的N的阶乘过大, 而且多组询问, T也过大 ,而且需要模不同的M (即可能不能离线求).
考虑到对于大于10000的素数 最多除一次 所以单独考虑 即把前面1229个素数和后面第1230个素数到最后一个素数分开考虑 :前面的暴力除,复杂度1229*logN
后面部分分块 把除数相同的合并. 然后快速幂, 复杂度logN*logN
所以最后的复杂度是O(T*1230*logN)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e8;
const int Mod=1e9+;
int p[],vis[maxn+],cnt;
void prime()
{
for(int i=;i<=maxn;i++){
if(!vis[i]) p[++cnt]=i;
for(int j=;j<=cnt&&(ll)i*p[j]<=maxn;j++){
vis[i*p[j]]=;
if(!(i%p[j])) break;
}
}
}
int qpow(int a,int x,int M){
int res=;
while(x){
if(x&) res=(ll)res*a%M;
a=(ll)a*a%M; x>>=;
} return res;
}
int main()
{
int T,i,j,x,M,pos,ans;
prime(); scanf("%d",&T);
for(i=;i<=T;i++){
ans=; scanf("%d%d",&x,&M);
for(j=;j<&&p[j]<=x;j++){ //暴力部分
int tmp=x,num=;
while(tmp){
num+=tmp/p[j]; tmp/=p[j];
}
ans=(ll)ans*(num+)%M;
}
pos=upper_bound(p+,p+cnt+,x)-p; pos--;
int fcy;
for(j=;j<=pos;j=fcy+){ //合并部分
fcy=upper_bound(p+,p+cnt+,x/(x/p[j]))-p; fcy--;
if(fcy>pos) fcy=pos;
ans=(ll)ans*qpow(x/p[j]+,fcy-j+,M)%M;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- Windows平台分布式架构实践 - 负载均衡
- HTML5 progress和meter控件
- vue.js学习(第一课)
- Codeforces Round #388 (Div. 2) - C
- iOS 2D绘图 (Quartz2D)之路径(stroke,fill,clip,subpath,blend)
- 实现PageProcessor
- 【转】持久化消息队列之MEMCACHEQ
- 使用saripaar对android输入控件进行快速验证
- CListView虚拟列表
- 日志管理 rsyslog服务浅析
- winform访问url传参有返回值
- Git中的fetch和pull
- Android(java)学习笔记173:BroadcastReceiver之 静态注册 和 动态注册
- iphone/ipad前端开发技巧
- 【2017-05-04】winfrom进程、线程
- Host &#39;hello-PC&#39; is not allowed to connect to this MySQL server远程连接mysql授权
- mysql-connector-java 6.x 时区设置
- Android反编译获取源码-android学习之旅(70)
- scrapy设置代理的方法
- Java中,多态的实现有哪些要求?实现多态的关键技术?