BZOJ2186: [Sdoi2008]沙拉公主的困惑

2186: [Sdoi2008]沙拉公主的困惑

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 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

Sample Output

1

数据范围：
对于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
",k);
106     }
107 
108     return 0;
109 
110 }

View Code

这是一道综合而又漂亮的好题！