首页 > 代码库 > BZOJ 2186 SDOI2008 沙拉公主的困惑 数论
BZOJ 2186 SDOI2008 沙拉公主的困惑 数论
题目大意:给定询问组数T和取模数P,每次询问给定两个整数n和m,求1~(n!)的数中与m!互质的数个个数模P (m<=n)
首先T<=1W,暴力肯定过不去,我们须要预处理一些东西
首先我们知道,若x与y互质,则x+y与y也互质,x+2y与y也互质。。。
换到这道题上来说,若一个数x与m!互质,那么x+(m!)也一定与m!互质,(x+m!*2)也一定与m!互质。。。
因为n!一定是m!的倍数,于是我们每存在到一个x<=m!与m!互质,我们就一定能找到(n!)/(m!)个与m!互质的数
而m!以内与m!互质的数的数量恰好是φ(m!)
于是我们要得到的数恰好就是φ(m!)*(n!)/(m!) %p
当中m!的全部质因数恰好就是m以内全部的质数 于是φ(m!)=(m!)*∏(pi-1)/pi (pi<=m)
于是最后我们的结果就是n!*∏(pi-1)/pi
质数预处理出来,n!预处理出来,pi的逆元预处理出来,∏(pi-1)/pi就能够预处理出来,都是线性的
至于pi的逆元 有一个比較快的线性求法(详见 http://blog.csdn.net/whyorwhnt/article/details/19169035 )
我的代码最后交上去超时了1.5秒AC。。。并且我还不是最慢的,wulala大神比我还要慢200+MS。。。
#include<bitset> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 10000001 using namespace std; typedef long long ll; bool not_prime[M+100]; ll prime[500500],ans[M+100],fac[M+100],rev[M+100]; int n,m,p,T,tot; void Linear_Shaker() { ll i,j; for(i=2;i<=M;i++) { if(!not_prime[i]) prime[++tot]=i; for(j=1;j<=tot&&prime[j]*i<=M;j++) { not_prime[prime[j]*i]=1; if(i%prime[j]==0) break; } } fac[1]=1; for(i=2;i<=M;i++) fac[i]=fac[i-1]*i%p; rev[1]=1; for(i=2;i<=M&&i<p;i++) rev[i]=(p-p/i)*rev[p%i]%p; ans[1]=1; for(i=2;i<=M;i++) { if(!not_prime[i]) ans[i]=ans[i-1]*(i-1)%p*rev[i%p]%p; else ans[i]=ans[i-1]; } } int main() { scanf("%d%d",&T,&p); Linear_Shaker(); for(int i=1;i<=T;++i) { scanf("%d%d",&n,&m); printf("%d\n",fac[n]*ans[m]%p); } }
BZOJ 2186 SDOI2008 沙拉公主的困惑 数论
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。