首页 > 代码库 > 【BZOJ2186】[Sdoi2008]沙拉公主的困惑 线性筛素数
【BZOJ2186】[Sdoi2008]沙拉公主的困惑 线性筛素数
【BZOJ2186】[Sdoi2008]沙拉公主的困惑
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
4 2
Sample Output
1
数据范围:
对于100%的数据,1 < = N , M < = 10000000
数据范围:
对于100%的数据,1 < = N , M < = 10000000
题解:跟欧拉函数的求法类似,就是找出1-m中所有的素数pi,再将n!分别乘上(pi-1)/pi就行了
#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long ll;ll n,m,mod,T,num;int p[10010];int pri[1000000];int jc[10000010],jpc[10000010];bool np[10000010];ll pm(ll x,ll y){ ll z=1; while(y) { if(y&1) z=z*x%mod; x=x*x%mod,y>>=1; } return z;}int main(){ scanf("%d%d",&T,&mod); int i,j; jc[1]=jpc[1]=1; for(i=2;i<=10000000;i++) { jc[i]=1ll*jc[i-1]*i%mod,jpc[i]=jpc[i-1]; if(!np[i]) pri[++num]=i,jpc[i]=1ll*jpc[i]*(i-1)%mod*pm(i,mod-2)%mod; for(j=1;j<=num&&1ll*i*pri[j]<=10000000;j++) { np[i*pri[j]]=1; if(i%pri[j]==0) break; } } while(T--) { scanf("%d%d",&n,&m); printf("%lld\n",1ll*jc[n]*jpc[m]%mod); } return 0;}
【BZOJ2186】[Sdoi2008]沙拉公主的困惑 线性筛素数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。