「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
题解
显然题目是求phi（m!) * ( n! / m!)
phi (m!) = m! * (p-1)/p p是m!的质因数
整理得 求 n! * (p-1)/p p是m!的质因数，即
预处理1-10000000的素数以及1-10000000的逆元。。。
都可以线性筛。。事实上只要把素数的逆元用exgcd求一求就好，其余并未用到
阶乘取模也预处理一下
————————————–
补下逆元求法
实际上由于其是积性函数，用exgcd求出素数逆元后就能在素数筛法时顺便求
还有递推求法
设R=ai+b
求F(i)
则 -a i = b (mod R) 同除以ib得
F(i) = – a F(b)
ine[i]=(R-R/i*ine[R%i]%R);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define N 10000000 #define ll long long using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int T,R,n,m,cnt; int fac[10000005],ine[10000005],pri[500005],ans[10000005]; bool mark[10000005]; void exgcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return;} exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; } int getine(int t) { int x,y; exgcd(t,R,x,y); return (x%R+R)%R; } void pre() { fac[1]=1;for(int i=2;i<=N;i++)fac[i]=(ll)fac[i-1]*i%R; ine[1]=1; for(int i=2;i<=N;i++) { if(!mark[i])pri[++cnt]=i,ine[i]=getine(i); for(int j=1;pri[j]*i<=N&&j<=cnt;j++) { mark[pri[j]*i]=1; //ine[pri[j]*i]=(ll)ine[pri[j]]*ine[i]%R; if(i%pri[j]==0)break; } } ans[1]=1; for(int i=2;i<=N;i++) { ans[i]=ans[i-1]; if(!mark[i])ans[i]=(ll)ans[i]*(i-1)%R*ine[i]%R; } } int main() { T=read();R=read(); pre(); while(T--) { n=read();m=read(); printf("%d\n",(ll)fac[n]*ans[m]%R); } return 0; } |
递推逆元
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define N 10000000 #define ll long long using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int T,R,n,m,cnt; int fac[10000005],ine[10000005],pri[500005],ans[10000005]; bool mark[10000005]; void pre() { fac[1]=1;for(int i=2;i<=N;i++)fac[i]=(ll)fac[i-1]*i%R; ine[1]=1; for(int i=2;i<=N;i++) { if(!mark[i])pri[++cnt]=i; for(int j=1;pri[j]*i<=N&&j<=cnt;j++) { mark[pri[j]*i]=1; if(i%pri[j]==0)break; } } for(int i=2;i<=N&&i<R;i++) ine[i]=(R-(ll)R/i*ine[R%i]%R); ans[1]=1; for(int i=2;i<=N;i++) { ans[i]=ans[i-1]; if(!mark[i])ans[i]=(ll)ans[i]*(i-1)%R*ine[i%R]%R; } } int main() { T=read();R=read(); pre(); while(T--) { n=read();m=read(); printf("%d\n",(ll)fac[n]*ans[m]%R); } return 0; } |
计数器 9317778
OI 课件=>
OI 课件=>
建议测试一组数据：
1 3
4 3
答案是:4!/3!*phi[3!]%3=2
您的程序跑出来的是0
我认为应该对模数分类做
大于107的求逆
小于107的卢卡斯
。。 我分析了下这组数据和黄学长公式中出现的问题，这组数据是因为R=R的那些R的倍数的数是没有逆元的，估计出题人的标程就是这种做法却忽略了这类情况所以没有在数据范围中给出R,m的大小关系，其实这种数据只要特判一下n,m,R的大小关系就可以处理了。
更正一下，应该是当m>=R的时候，求phi(m!)的时候用到的(R-1)/R，而R不存在关于模R的逆元。
p是小于m!的所有质数是在搞笑吗？
这不科学