[BZOJ2186]沙拉公主的困惑
2024-10-20 05:15:18
[BZOJ2186]沙拉公主的困惑
题面
大富翁国因为通货膨胀,以及假钞泛滥,政府决定推出一项新的政策:现有钞票编号范围为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 11luog
4 2
Sample Output
1
数据范围: 对于100%的数据,1 < = N , M < = 10000000
思路
易证如果\(n\)为\(m\)的倍数,那么\([1,n]\)中和\(m\)互素的数的个数为$\frac {n} {m}\phi(m) \(。那么\)[1,N!]\(中和\)M!\(互素的个数就是\)\frac{N!}{M!}\phi(M!)$。那么预处理出所有数的阶乘。再来考虑解决欧拉函数的处理。
\(\phi(M!)=M!*\frac{\prod_{i=1}^{j}(p_i-1)}{\prod _{i=1}^{j}p_i}\),显然,\(\forall p_i,p_i\leq m\)。那我们前缀和(积)一波就可以了。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define mod r
#define ll long long
#define maxn (int)(1e7+100)
int t,r;
ll factu[maxn];
ll prodd[maxn],produ[maxn];
ll ksm(ll num,ll times){
ll ans = 1 , cur = num % mod;
while( times ) {
if( times & 1 ) ans *= cur , ans %= mod;
cur *= cur , cur %= mod , times >>= 1;
}
return ans;
}
void init(){
factu[1]=1;
for(int i=2;i<maxn;i++){
factu[i]=(ll)factu[i-1]*i;factu[i]%=mod;
}
static bool mark[maxn+1000]={0};
produ[1]=1,prodd[1]=1;
for(int i=2;i<maxn;i++){
produ[i]=produ[i-1];prodd[i]=prodd[i-1];
if(mark[i]){continue;}
produ[i]*=(i-1);produ[i]%=mod;
prodd[i]*=i;prodd[i]%=mod;
for(int j=i;j<maxn;j+=i)mark[j]=1;
}
return;
}
void solve(){
ll n,m;scanf("%lld%lld",&n,&m);
if(n>=mod&&m<mod){puts("0");return;}
ll ans=factu[n];ans%=mod;
ans*=(produ[m]*ksm(prodd[m],mod-2)%mod)%mod;
ans%=mod;
printf("%lld\n",ans);
}
int main(){
//freopen("in","r",stdin);
scanf("%d%d",&t,&r);
init();
while(t--)solve();
return 0;
}
最新文章
- Linux用户态和内核态
- [BI项目记]-文档版本管理笔记
- xcode6.0以上创建一个Empty Application
- 总结:视频播放的四种实现方案(Native)
- iOS之类的本质
- ios内购
- CocoaPods 安装的第三方删除
- 主题: 为kindsoft编辑器替换SyntaxHighlighter代码高亮,整合DEDECMS
- 解决node使用中8080端口被占用
- javascript如何获取URL参数的值
- 微信小程序 引入公共页面的几种情况
- ag使用需要注意的问题
- 项目中同一个dll的x86和x64同时引用
- iOS开发-使用宏自定义输出(NSLog)
- Android——列表视图 ListView(一)Arrayadapter
- (转)JSON Web Token - 在Web应用间安全地传递信息
- Meteor.js异步全解
- linux下php添加cur/soapl扩展
- 使用Apache的ab工具进行网站性能测试
- 十五.jQuery源码解析之Sizzle总体结构.htm