BZOJ 2186 沙拉公主的困惑(预处理逆元+欧拉函数)
2024-10-21 10:04:45
题意:求1-n!里与m!互质的数有多少?(m<=n<=1e6).
因为n!%m!=0,所以题目实际上求的是phi(m!)*n!/m!.
预处理出这些素数的逆元和阶乘的模即可。
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <bitset>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-
# define MOD
# define INF
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<,l,mid
# define rch p<<|,mid+,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int N=;
//Code begin... int fac[N], pri[N], inv[N], ans[N];
bool vis[N];
int P, tot;
void init(int n)
{
fac[]=;
FOR(i,,n) fac[i]=(LL)fac[i-]*i%P;
inv[]=;
FOR(i,,n){
if(!vis[i])pri[++tot]=i;
for(int j=; pri[j]*i<=n&&j<=tot; ++j){
vis[pri[j]*i]=;
if(i%pri[j]==) break;
}
}
for(int i=; i<=n&&i<P; ++i) inv[i]=(P-(LL)P/i*inv[P%i]%P);
ans[]=;
FOR(i,,n) {
ans[i]=ans[i-];
if(!vis[i])ans[i]=(LL)ans[i]*(i-)%P*inv[i%P]%P;
}
}
int main()
{
int T, n, m; scanf("%d%d",&T,&P); init(N-);
while(T--){
scanf("%d%d",&n,&m);
printf("%d\n",(LL)fac[n]*ans[m]%P);
}
return ;
}
最新文章
- java.lang.Class<;T>; -- 反射机制
- java 小程序--杨辉三角
- 网络粘贴---Xcode中可用到的快捷键
- Redis多机功能之Sentinel
- CODESOFT 2015中的条形码对象该如何创建
- Jquery插件placeholder的用法
- (16)IO流之输入字节流FileInputStream和输出字节流FielOutputStream
- Attribute name ";aphmodel"; associated with an element type ";mxg"; must be followed by the &#39; = &#39; charac
- Python 字符串常见的27个操作
- ASP.NET Core快速入门学习笔记(第1章:介绍与引入)
- DOM-节点概念-属性
- thunderbird 日历
- Maven解决NoPluginFoundForPrefixException错误
- C# -- 索引器、枚举类型
- (C/C++学习笔记) 二十三. 运行时类型识别
- 微信赌场——H5棋牌游戏渗透之旅
- Linux常用基本命令(xargs )
- Ubuntu dns
- BZOJ3688 折线统计 【dp + BIT】
- 让ie6(opera)支持微软雅黑字体
热门文章
- 基于Opencv的人脸检测及识别
- 20155323 2016-2017-2《Java程序设计》课程总结
- 我与虚拟机的初次接触及初探Liux命令 20155338
- 「Leetcode」975. Odd Even Jump(Java)
- Selenium2+python自动化-iframe
- 《Learning scikit-learn Machine Learning in Python》chapter1
- python打印图形大全(详解)
- mariadb BINLOG_FORMAT = STATEMENT 异常
- nginx 根据get参数重定向(根据电视访问的mac地址传递的值,来重定向访问别的url地址,这样就可以进行单台的测试环境。。)
- [二叉查找树] 1115. Counting Nodes in a BST (30)