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
如果 gcd(i,n)=1, 那么 gcd(i+n,1)=1.
于是答案 =$\varphi (m!)*(n!)/(m!)$
=$\varphi(m!)/(m!) *(n!)$
于是前面那个设为 f[m], 这个可以线筛出来, 同时推出逆元.
f[m] 其实就是 m 以内所有的质数 (p-1)/p 乘起来, 预处理即可.
代码:
- #include <stdio.h>
- #define LL long long
- int prim[5000001],n,m,t,p,env[10000001],fac[10000001],f[10000001],cnt;
- bool vis[10000001];
- int main()
- {
- scanf("%d%d",&t,&p);
- env[1]=1;
- fac[0]=fac[1]=1;
- f[1]=1;
- for(int i=2;i<=10000000;i++)
- {
- if(i<=p)
- env[i]=(p-p/i)*1ll*env[p%i]%p;
- else
- env[i]=env[i-p];
- if(!vis[i])
- {
- if(env[i]%p!=0)
- f[i]=1ll*f[i-1]*env[i]%p*(i-1)%p;
- else
- {
- f[i]=1ll*f[i-1]*(i-1)%p;
- }
- prim[cnt++]=i;
- }
- else f[i]=f[i-1];
- for(int j=0;j<cnt&&i*prim[j]<=10000000;j++)
- {
- vis[i*prim[j]]=1;
- if(i%prim[j]==0)break;
- }
- if(i%p!=0)fac[i]=1ll*fac[i-1]*i%p;
- else
- {
- int num=i;
- while(num%p==0)num/=p;
- fac[i]=fac[i-1]*num%p;
- }
- }
- while(t--)
- {
- scanf("%d%d",&n,&m);
- if(n>=p*2||(n>=p&&m<p))
- {printf("0\n");continue;}
- printf("%lld\n",1ll*f[m]*fac[n]%p);
- }
- }
来源: http://www.bubuko.com/infodetail-2651442.html