首页 > 代码库 > BZOJ2186: [Sdoi2008]沙拉公主的困惑
BZOJ2186: [Sdoi2008]沙拉公主的困惑
2186: [Sdoi2008]沙拉公主的困惑
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 1168 Solved: 352
[Submit][Status]
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
数论
题解:
这种数论题简直不能再orz,做法不能再炫酷。。。
首先 与m!互质的数的个数为 fai[m!],
又因为gcd(a+b,b)=gcd(a,n)
即比 m!大和它互质的数-m!的若干倍之后一定是 这fai[m!]中的一个,所以这样的数一共有 fai[m!]*(n!/m!) 个。。。
这个式子怎么求呢?
我们可以分成两部分来求 即fai[m!]/m! 和 fac[n]
而根据fai的展开式可以知道 fai[m!]/m!= 连积(p-1/p),满足p是<=m的质数 。。。(蒻蒻不会放图片。。。)
这样我们就可以预处理递推搞了,回答O(1)
oj上内存卡死,受不鸟了于是怒开临时变量存储中间结果。。。结果还是慢成翔啊。。。
代码:
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 10000000+5 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 using namespace std; 44 45 inline ll read() 46 47 { 48 49 ll x=0,f=1;char ch=getchar(); 50 51 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 52 53 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 54 55 return x*f; 56 57 } 58 int n,m,cs,mod,tot,p[maxn],fac[maxn],ans[maxn],inv[maxn]; 59 bool check[maxn]; 60 61 int main() 62 63 { 64 65 freopen("input.txt","r",stdin); 66 67 freopen("output.txt","w",stdout); 68 69 cs=read();mod=read(); 70 fac[0]=1; 71 for1(i,maxn) 72 { 73 ll k=fac[i-1];k*=i;k%=mod; 74 fac[i]=k; 75 } 76 for2(i,2,maxn) 77 { 78 if(!check[i])p[++tot]=i; 79 for1(j,tot) 80 { 81 ll k=i*p[j]; 82 if(k>maxn)break; 83 check[k]=1; 84 if(i%p[j]==0)break; 85 } 86 } 87 inv[0]=inv[1]=1; 88 for2(i,2,maxn) 89 { 90 ll k=inv[i-mod%i];k*=(mod/i+1);k%=mod; 91 inv[i]=k; 92 } 93 ans[1]=1; 94 for2(i,2,maxn) 95 if(!check[i]) 96 { 97 ll k=ans[i-1];k*=i-1;k%=mod;k*=inv[i%mod];k%=mod; 98 ans[i]=k; 99 }100 else ans[i]=ans[i-1];101 //for(ll i=1;i<=1000000;i++)cout<<i<<‘ ‘<<inv[i]<<‘ ‘<<ans[i]<<endl; 102 while(cs--)103 {104 n=read(),m=read();ll k=fac[n];k*=ans[m];k%=mod;105 printf("%lld\n",k);106 }107 108 return 0;109 110 }
这是一道综合而又漂亮的好题!
BZOJ2186: [Sdoi2008]沙拉公主的困惑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。