求在1到n!范围内，与m!互质的数的数量，由于答案太大，只需计算答案对R取模之后的答案即可，保证R是一个质数 对于30%的数据，n<=10，T<=30 对于60%的数据n<=3000000，T<=10000 对于100%的数据n<=10000000，T<=10000 保证R为质数，m<=n,n < R 题意很简单，，看见n<=10000000就知道要预处理。。 ans=phi（m!）*n!/m! =m!n!/m!(pi-1)/pi(pi是m!的质因数) =n!*(pi-1)/pi 所以这道题的难点就在于怎样预处理1-10000000的素数和逆元。 素数很简单，用欧拉筛法就可以了。 那么逆元呢？ 很可惜，，我问遍了很多人，结果只得到下面结论，，，并不知道怎么推的。。 p=na+b, b*b’=1, (p-na)*b’=1, -nab’=1 mod p, n’=-ab’ 用b’推n’ 然后可以得出i’=(p-trunc(p/i))*(p-i*trunc(p/i))’ mod p 很明了的式子呢。。可惜并不会手推，，我觉得能理解就最好不要记模板。。 下面是代码：
const maxn=10000000; var t,r,n,m,cnt,i,j:longint; fac:array[0..10000005]of longint; ine:array[0..10000005]of longint; pri:array[0..500005]of longint; ans:array[0..10000005]of longint; mark:array[0..10000005]of boolean; procedure pre; var i,j:longint; begin fac[1]:=1; for i:=2 to maxn do fac[i]:=int64(fac[i-1])*i mod r; ine[1]:=1; for i:=2 to maxn do begin if(not mark[i])then begin inc(cnt); pri[cnt]:=i; end; j:=1; while (pri[j]*i<=maxn)and(j<=cnt)do begin mark[pri[j]*i]:=true; if (i mod pri[j]=0)then break; inc(j); end; end; for i:=2 to maxn do if i<r then ine[i]:=((r-trunc(r/i))*ine[r-i*trunc(r/i)]mod r); ans[1]:=1; for i:=2 to maxn do begin ans[i]:=ans[i-1]; if(not mark[i])then ans[i]:=int64(ans[i])*(i-1)mod r*ine[i mod r]mod r; end; end; begin read(t,r); pre; while t<>0 do begin read(n,m); writeln(int64(fac[n])*ans[m]mod r); dec(t); end; end.