F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 2186. -- [Sdoi2008]沙拉公主的困惑

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

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 6108  Solved: 2066
[Submit][Status][Discuss]

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

[Submit][Status][Discuss]

HOME Back