BZOJ 2186 沙拉公主的困惑
2024-10-14 14:39:50
2186: [Sdoi2008]沙拉公主的困惑
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 3397 Solved: 1164
[Submit][Status][Discuss]
Description
大富翁国因为通货膨胀,以及假钞泛滥,政府决定推出一项新的政策:现有钞票编号范围为1到N的阶乘,但是,政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在,请你帮助沙拉公主解决这个问题,由于可能张数非常大,你只需计算出对R取模后的答案即可。R是一个质数。
Input
第一行为两个整数T,R。R<=10^9+10,T<=10000,表示该组中测试数据数目,R为模后面T行,每行一对整数N,M,见题目描述
m<=n
Output
共T行,对于每一对N,M,输出1至N!中与M!素质的数的数量对R取模后的值
Sample Input
1 11
4 2
Sample Output
1
数据范围:
对于100%的数据,1 < = N , M < = 10000000
HINT
Source
代码
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e7+;
//const int M=N/10;
bool check[N]={,};
int n,m,mod,tot,T;
//int prime[M];
ll ans1[N],ans2[N],inv[N];
/*void get_prime(){
for(int i=2;i<N;i++){
if(!check[i]) prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++){
check[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}*/
//面向std编程,不要问我为什么
void get_prime(){
int m=sqrt(N+0.5);
for(int i=;i<=m;i++){
if(!check[i]){
for(int j=i*i;j<N;j+=i){
check[j]=;
}
}
}
}
int main(){
//freopen("sh.txt","r",stdin);
get_prime();
scanf("%d%d",&T,&mod);
ans1[]=;
for(int i=;i<N;i++) ans1[i]=ans1[i-]*i%mod;
inv[]=;
for(int i=;i<N;i++){
if(i>=mod) break;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
ans2[]=;
for(int i=;i<N;i++){
if(!check[i]){
ans2[i]=ans2[i-]*(i-)%mod;
ans2[i]=ans2[i]*inv[i%mod]%mod;
}
else ans2[i]=ans2[i-];
}
while(T--){
scanf("%d%d",&n,&m);
ll ans=ans1[n]*ans2[m]%mod;
printf("%lld\n",ans);
}
return ;
}
最新文章
- 【sdoi2013】森林 BZOJ 3123
- Compute Resource Consolidation Pattern 计算资源整合模式
- FMDB第三方框架
- win7升win10,初体验
- 非对称加密RSA的应用及在C#中的实现
- C++ 的语言杂谈(一)--C++不是新手友好的
- 算法系列8《Base64》
- Windows系统下Memcached缓存系列二:CouchbaseClient(c#客户端)的详细试用,单例模式
- c++ (P49—P68)
- 【转】Objective-C并发编程:API和挑战
- windows平台下基于QT和OpenCV搭建图像处理平台
- 43.Linux调试测试输入思路
- 《C#并发编程经典实例》学习笔记—2.3 报告任务
- Selenium 汇总
- CHECK约束表达式
- django xlwt实现资产导出功能
- VS2017gets的使用
- Caffe使用: Ubuntu 14.04(x64) 从cuda 7.0 升级到 cuda8.0
- Matlab 随机数字
- Goroutines和Channels(三)
热门文章
- java设计模式——享元模式
- jquery 操作css 尺寸
- javascript中call,apply,bind的使用
- React dangerouslySetInnerHTML - 将HTML字符串解析为html样式显示
- 基于asp.net MVC 的服务器和客户端的交互(一)
- 【清真dp】cf1144G. Two Merged Sequences
- 【赛时总结】 ◇赛时&#183;II◇ AtCoder ABC-100
- PHP中json_encode后,在json字符串中依然显示中文的解决方案
- Linux系统崩溃,数据迁移
- IntelliJ IDEA 12 创建Web项目 教程 超详细版【转】