首页 > 代码库 > Bzoj2186 [Sdoi2008]沙拉公主的困惑
Bzoj2186 [Sdoi2008]沙拉公主的困惑
Submit: 4100 Solved: 1424
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
HINT
Source
数学问题 欧拉函数
与M!互质的钞票数,显然就是$ \phi(M!) $
直接按照公式计算,
$ \phi(M!) = M! * \Pi(1- \frac{1}{p_i}) = M!*\Pi ((p_i-1)/p_i)$ ($p_i$是M!的质因数)
当n>=m时,$N!$显然是$M!$的倍数,那么答案就是
$\frac{N!}{M!}*\phi(M!)$,
约分一下得到
$ N!* \Pi ((p_i-1)/p_i) $。
发现每次询问的模数是固定的,那么可以线性预处理出
$ \Pi ((p_i-1)/p_i) $
回答询问时乘个$ N! $即可。
↑除的部分要改成逆元
迷之困,写一半忘了自己要写什么,把phi什么的都筛出来了,把逆元求了阶乘,之后发现根本用不到
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=10000005; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}13 return x*f;14 }15 int pri[mxn],cnt=0;16 int fac[mxn],inv[mxn];17 bool vis[mxn];18 int T,P;19 int ans[mxn];20 void init(){21 fac[0]=fac[1]=1;inv[0]=inv[1]=1;22 int i,j;23 for(i=2;i<mxn;i++){24 fac[i]=(LL)fac[i-1]*i%P;25 inv[i]=((-P/i*(LL)inv[P%i])%P+P)%P;26 }27 for(i=2;i<mxn;i++){28 if(!vis[i]){pri[++cnt]=i;}29 for(j=1;j<=cnt && (LL)i*pri[j]<mxn;j++){30 vis[i*pri[j]]=1;31 if(i%pri[j]==0){break;}32 }33 }34 ans[1]=1;35 for(i=2;i<mxn;i++){36 ans[i]=ans[i-1];37 if(!vis[i])ans[i]=(LL)ans[i]*(i-1)%P*inv[i]%P;38 }39 return;40 }41 int main(){42 int i,j;43 T=read();P=read();44 init();int n,m;45 while(T--){46 n=read();m=read();47 printf("%d\n",(LL)ans[m]*fac[n]%P);48 }49 return 0;50 }
Bzoj2186 [Sdoi2008]沙拉公主的困惑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。