φ(1)=1 [Sdoi2008]沙拉公主的困惑_综合


   
    问题 F: [Sdoi2008]沙拉公主的困惑
    时间限制: 1 Sec  
    内存限制: 259 MB
   题目描述
   
    
    大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。
   
输入
   
    
    第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n
   
输出
   
    共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值
   
样例输入1 11 4 2

样例输出
1数据范围：
对于100%的数据，1 < = N , M  < = 10000000



x与y互质 x+y ,x+2y,x+3y~~~ 与y互质
 则x与m!互质 x+m!,m+2*m!,x+3*m!~~~ 互质 
 有n！/m！ -》
φ(m!)*(n!/m!)%mod 
φ(m!)=m!* ∏（Pi-1)/Pi 
ans=n!* ∏（Pi-1)/Pi 

1：编译错误 线性
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define V 10000005
#define LL long long
using namespace std;
int n,m,t,mod;
bool ist[V+100]={1,1};
LL rev[V];
int ns; LL 有问题
LL p[600000],mb[V+100],pp[V],ans;
LL zz;
inline void pre()
{LL i,j;for(i=2;i<V-2;i++){if(!ist[i]){p[ns++]=i;}for(j=0;j<ns&&i*p[j]<V-2;j++){ist[i*p[j]]=1;if(!(i%p[j]))break;}} rev[1]=1;for(i=2;i<V-2&&i<mod;i++)rev[i]=(mod-mod/i)*rev[mod%i]%mod;zz=1;for(i=1;i<V-2;i++){zz*=i;zz%=mod;mb[i]=zz;}pp[1]=1;for(i=2;i<V-2;i++){if(!ist[i])pp[i]=pp[i-1]*(i-1)%mod*rev[i%mod]%mod;elsepp[i]=pp[i-1];	 	}}
int main()
{
//freopen("in.txt","r",stdin);
cin>>t>>mod;pre();//cout<<ns<<endl;while(t--){scanf("%d%d",&n,&m);printf("%lld\n",mb[n]*pp[m]%mod);}return 0;	 
}
2：过不去的编译 BZOJ A
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<algorithm>
#define V 1000003
#define LL long long
using namespace std;
int n,m,t,mod;
LL p[700000],ist[V]={1,1},ns,md,mb[V],pp[700000],ans;
LL zz;
inline void pre()
{for(int i=2;i<V-2;i++){if(!ist[i]){p[ns++]=i;}for(int j=0;j<ns&&i*p[j]<V;j++){ist[i*p[j]]=1;if(!(i%p[j]))break;}}memset(ist,0,sizeof(ist));ist[1]=1;for(int i=2;i<V&&i<mod;i++)ist[i]=(mod-mod/i)*ist[mod%i]%mod;zz=1;for(int i=1;i<V-2;i++){zz*=i;zz%=mod;mb[i]=zz;}pp[0]=ist[p[0]]*(p[0]-1)%mod;for(int i=1;i<ns;i++){pp[i]=pp[i-1]*(p[i]-1)*ist[p[i]]%mod;	 	}
}
inline int haha()
{//freopen("then.in","r",stdin);//freopen("then.out","w",stdout);// freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);//freopen("nt2011_travel.in","r",stdin);freopen("nt2011_travel.out","w",stdout);cin>>t>>mod;pre();//cout<<ns<<endl;while(t--){cin>>n>>m;ans=mb[n];for(int i=0;i<ns;i++)if(p[i]>m){if(i==0)break;ans*=pp[i-1];ans%=mod;break;}cout<<ans<<endl;}//while(1);return 0;	 
}
int gg=haha();
int main()
{;}





#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<algorithm>
#define V 1000007
#define LL long long
using namespace std;
int n,m,t,mod;
LL p[V],ist[V]={1,1},ns,md,mb[V],ans;
LL zz;
LL qp(LL x,LL y)
{zz=1;while(y){if(y&1)zz=(LL)zz*x%mod;x=(LL)x*x%mod;y>>=1;}return zz;
}
inline void pre()
{for(int i=2;i<V-2;i++){if(!ist[i]){p[ns++]=i;}for(int j=0;j<ns&&i*p[j]<V;j++){ist[i*p[j]]=1;if(!(i%p[j]))break;}}memset(ist,0,sizeof(ist));zz=1;for(int i=1;i<V-2;i++){zz*=i;zz%=mod;mb[i]=zz;}ans=1;for(int i=0;i<ns;i++){ans*=(p[i]-1)*qp(p[i],mod-2)%mod;ans%=mod;ist[i]=ans;}
}
inline int haha()
{cin>>t>>mod;pre();while(t--){cin>>n>>m;ans=mb[n];for(int i=0;i<ns;i++)if(p[i]>m){if(i==0)break;ans*=ist[i-1];ans%=mod;break;}cout<<ans<<endl;}//while(1);return 0;	 
}
int gg=haha();
int main()
{;}





5
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<algorithm>
#define V 1000009
#define LL long long
using namespace std;
int n,m,t,mod;
LL p[V],ist[V]={1,1},ns,md,mb[V],ans;
LL qp(LL x,LL y)
{LL zz=1;while(y){if(y&1)zz=(LL)zz*x%mod;x=(LL)x*x%mod;y>>=1;}return zz;
}
inline void pre()
{for(int i=2;i<V-2;i++){if(!ist[i]){p[ns++]=i;}for(int j=0;j<ns&&i*p[j]<V;j++){ist[i*p[j]]=1;if(!(i%p[j]))break;}}memset(ist,0,sizeof(ist));LL zz=1;for(int i=1;i<V-2;i++){zz*=i;zz%=mod;mb[i]=zz;}ans=1;for(int i=0;i<ns;i++){ans*=(p[i]-1)*qp(p[i],mod-2)%mod;ans%=mod;ist[i]=ans;}
}
inline int haha()
{cin>>t>>mod;pre();while(t--){cin>>n>>m;ans=mb[n];for(int i=0;i<ns;i++)if(p[i]>m){if(i==0)break;ans*=ist[i-1];ans%=mod;break;}cout<<ans<<endl;}//while(1);return 0;	 
}
int gg=haha();
int main()
{;}