[SDOI 2008]沙拉公主的困惑
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
4 2
Sample Output
1
HINT
数据范围:
对于100%的数据,1 < = N , M < = 10000000
题解
首先显然在区间 $[1, M!]$ 内与 $M!$ 互素的数个数为 $\varphi(M!)$ 。
我们再考虑比 $M!$ 大的个数,值得注意的是我们存在这样一个性质:若 $x$ 与 $i$ (不)互质,则 $x+i$ 与 $i$ (不)互质。简要证明下:
现在我们证明对于整数 $x$ 若与 $i$ 互质,则 $x+i$ 也与 $i$ 互质。
采用反证法,我们假设 $gcd(x, i) = 1$ 但 $gcd(x+i, i) = b \neq 1$ 。
容易发现: \begin{cases} \begin{aligned} x+i = b\cdot k_1 \\ i = b \cdot k_2 \end{aligned} \end{cases} $k_1,k_2$ 均为整数。
所以 $x = (k_1-k_2)\cdot b$ ,故 $gcd(x, i) = b \neq 1$ ,与题设不符,原命题成立。
下证对于整数 $x$ 若与 $i$ 不互质,则 $x+i$ 也与 $i$ 不互质。
假设
$gcd(x, i) = b \neq 1$ , \begin{cases} \begin{aligned} x = b\cdot k_1
\\ i = b \cdot k_2 \end{aligned} \end{cases}$k_1,k_2$ 均为整数。
所以 $x+i = (k_1+k_2)\cdot b$ ,故 $gcd(x+i, i) = b \neq 1$ ,原命题成立。
故该题的答案
\begin{aligned} ans &= \varphi(M!) \cdot \frac{N!}{M!} \\ &= M! \cdot \prod_{p\mid M!,p~is~a~prime} \left( 1-\frac{1}{p} \right)\cdot \frac{N!}{M!} \\ &= N! \cdot \prod_{p\mid M!,p~is~a~prime} \frac{p-1}{p} \end{aligned}
因为 $M!$ 素因数是连续的一段,所以我们只要统计 $[1, M!]$ 中的所有素数积的逆元,以及所有素数 $-1$ 的乘积即可。
ps:其实这道题是有 $bug$ 的,我们注意到用线性求逆元时求的数是不能大于等于模数的,而题面中并没有强调模数 $P$ 恒大于 $N$ 和 $M$ ,将错就做吧。
//It is made by Awson on 2018.1.12
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
using namespace std;
const int N = 1e7;
void read(int &x) {
char ch; bool flag = ;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());
for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());
x *= -*flag;
}
void write(int x) {
if (x > ) write(x/);
putchar(x%+);
} int t, n, m, p, inv[N+], pro[N+];
int prime[N+], isprime[N+], tot, A[N+], B[N+]; void pre() {
pro[] = inv[] = ; for (int i = ; i <= N; i++) pro[i] = (LL)i*pro[i-]%p, inv[i] = -(LL)p/i*inv[p%i]%p;
for (int i = ; i <= N; i++) {
if (!isprime[i]) prime[++tot] = i;
for (int j = ; j <= tot && i*prime[j] <= N; j++) {
isprime[i*prime[j]] = ; if (!(i%prime[j])) break;
}
}
A[] = B[] = , A[prime[]] = (prime[]-)%p, B[prime[]] = inv[prime[]]%p;
for (int i = ; i <= tot; i++) A[prime[i]] = (LL)A[prime[i-]]*(prime[i]-)%p, B[prime[i]] = (LL)B[prime[i-]]*inv[prime[i]]%p;
for (int i = ; i <= N; i++) {if (!A[i]) A[i] = A[i-]; if (!B[i]) B[i] = B[i-]; }
}
void work() {
read(t), read(p);
pre(); while (t--) {
read(n), read(m); write(((LL)pro[n]*A[m]%p*B[m]%p+p)%p); putchar('\n');
}
}
int main() {
work();
return ;
}
最新文章
- VS 与JIRA Bamboo的连接
- thread.join 从异步执行变成同步
- lightoj1348
- iOS10以及xCode8相关资料收集
- block反向界面传值
- jquery 点击事件
- FL2440驱动添加(1):hello world 驱动模块添加
- java中判断字符串是否为数字的方法
- java socket通讯(一) 入门示例
- python pdb调试
- 支持向量机(SVM)算法的matlab的实现
- FusionCharts参数说明-----3D饼图属性(Pie3D.swf )
- fstab的格式
- hdu-4302-Holedox Eating-线段树-单点更新,有策略的单点查询
- 转:Cocoa、Foundation、UIKit、Objective-c、XCode、Interface Builder的概念
- cobbler自动安装系统
- pycharm中的光标变粗的问题
- webpack(5)--Resolve
- andorid ListView和GirdView 与ScrollView 冲突
- ASP.NET WebApi总结之自定义权限验证