首页 > 代码库 > 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
正解:欧拉函数+线性筛。
比较基础的一道数论题,不过很卡常数。。
首先,若$(x,y)=1$,根据欧几里得定理可得,$(x+y,y)=1$。
那么在$m!$以内,与$m!$互质的数有$\varphi (m!)$个,又因为$n!$肯定是$m!$的倍数,所以$Ans=\varphi (m!)*\frac{n!}{m!}$
注意到$m!$的质因子为$\leq m$的所有质数,于是$\varphi (m!)=m!*\prod \frac{x-1}{x}$,其中$x\leq m$且$x$为质数。
所以$Ans=n!*\prod \frac{x-1}{x}$,那么现在就很简单了,预处理出逆元,阶乘,和连乘后面那一坨东西,然后直接带入算答案就行了。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define N (10000010)14 #define inf (1<<30)15 #define il inline16 #define RG register17 #define ll long long18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)19 20 using namespace std;21 22 ll phi[N],fac[N],inv[N],prime[N/5],n,m,p,cnt;23 bool vis[N];24 25 il ll gi(){26 RG ll x=0,q=1; RG char ch=getchar();27 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();28 if (ch==‘-‘) q=-1,ch=getchar();29 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();30 return q*x;31 }32 33 il void pre(){34 fac[0]=fac[1]=inv[1]=phi[1]=1;35 for (RG ll i=2;i<N && i<p;++i) inv[i]=(p-p/i)*inv[p%i]%p;36 for (RG ll i=2;i<N;++i){37 fac[i]=fac[i-1]*i%p;38 if (!vis[i]) prime[++cnt]=i,phi[i]=(i-1)*inv[i%p]%p;39 if (!phi[i]) phi[i]=phi[i-1]; else (phi[i]*=phi[i-1])%=p;40 for (RG ll j=1,k;j<=cnt;++j){41 k=i*prime[j]; if (k>=N) break;42 vis[k]=1; if (!(i%prime[j])) break;43 }44 }45 return;46 }47 48 il void work(){49 n=gi(),m=gi();50 printf("%lld\n",phi[m]*fac[n]%p); return;51 }52 53 int main(){54 File("princess");55 RG ll T=gi();56 p=gi(),pre();57 while (T--) work();58 return 0;59 }
bzoj2186 [Sdoi2008]沙拉公主的困惑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。