大视野2186: 沙拉公主的困惑(求逆元）

大视野2186: 沙拉公主的困惑(求逆元）

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

Time Limit: 10 Sec   Memory Limit: 259 MB

Submit: 2616   Solved: 880

[ ​​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

代码：

#include #include #include #include using namespace std;typedef long long LL;const int N = 10000005;bitset prime;void isprime(){ prime.set(); for(int i=2; i= MOD) break; inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; } ans2[1] = 1; for(int i=2; i

接下来还有一个关于逆元的有意思的题目，描述如下

证明完毕！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。