首页 > 代码库 > 2186: [Sdoi2008]沙拉公主的困惑 - BZOJ

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

2024-07-06 10:17:38   229人阅读

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

 

 

 

卧槽，这也坑，Wikioi竟然有两个点的R不是质数。。。。。。

还好BZOJ上没有坑，其实打扩展欧几里得比i^(r-2)要快，但是既然他是质数，我当然要好好利用一下了

就是m!*φ(n)/n!，然后预处理m!和φ(n)/n!就行了

 1 const
 2     maxn=10000000;
 3     maxq=10000;
 4 var
 5     t,r,max,tot:longint;
 6     flag:array[0..maxn]of boolean;
 7     a,b:array[0..maxn]of int64;
 8     n,m:array[0..maxq]of longint;
 9     p:array[0..1000000]of longint;
10     x,y:int64;
11 
12 procedure extendedgcd(a,b:longint);
13 var
14     t:int64;
15 begin
16     if b=0 then
17     begin
18       x:=1;
19       y:=0;
20       exit;
21     end;
22     extendedgcd(b,a mod b);
23     t:=x;
24     x:=y;
25     y:=t-(a div b)*y;
26 end;
27 
28 procedure pre;
29 var
30     i,j:longint;
31 begin
32     for i:=2 to max do
33       begin
34         if flag[i]=false then
35         begin
36           inc(tot);
37           p[tot]:=i;
38         end;
39         for j:=1 to tot do
40           begin
41             if int64(i)*p[j]>max then break;
42             flag[i*p[j]]:=true;
43             if i mod p[j]=0 then break;
44           end;
45       end;
46     a[0]:=1;
47     b[0]:=1;
48     flag[1]:=true;
49     for i:=1 to max do
50       begin
51         a[i]:=a[i-1]*i mod r;
52         if flag[i] then b[i]:=b[i-1]
53         else
54           begin
55             extendedgcd(i,r);
56             if x<0 then x:=x+trunc(x/r)*r+r;
57             x:=x mod r;
58             b[i]:=(b[i-1]*(i-1)mod r)*x mod r;
59           end;
60       end;
61 end;
62 
63 procedure main;
64 var
65     i:longint;
66 begin
67     read(t,r);
68     for i:=1 to t do
69       begin
70         read(n[i],m[i]);
71         if n[i]>max then max:=n[i];
72       end;
73     pre;
74     for i:=1 to t do
75       writeln(a[n[i]]*b[m[i]] mod r);
76 end;
77 
78 begin
79     main;
80 end.
View Code

 


联系
我们