当前位置:网站首页>快速幂模板求逆元,逆元的作用以及例题【第20届上海大学程序设计联赛夏季赛】排列计数
快速幂模板求逆元,逆元的作用以及例题【第20届上海大学程序设计联赛夏季赛】排列计数
2022-07-06 11:18:00 【吴雨4】
乘法逆元的定义
若整数 b,m 互质,并且对于任意的整数 a,如果满足 b|a(整除),则存在一个整数 x,使得 a/b≡a*x(mod m),则称 x 为 b 的模 m 乘法逆元,记为 (mod m)。 b存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m为质数时, 即为 b 的乘法逆元。
所以可以用快速幂的模板求解逆元。
题面:
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
//快速幂模板
int qmi(int a,int k,int p)
{
int res=1;
while(k)
{
if(k&1) res=(ll)res*a%p;
k>>=1;
a=(ll) a*a%p;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
while(n--)
{
ll a,p;
cin>>a>>p;
if(a%p) cout<<qmi(a,p-2,p)<<endl;//只有当a不是p的倍数时,才有逆元。
//若a是p的倍数,则有a/b=0,不会同余于a*x了,即无逆元。
else cout<<"impossible"<<endl;
}
return 0;
}
那我们来说说逆元的作用吧
先来说说加减乘除的求余概念
(a + b) % p = (a%p + b%p) %p (√)
(a - b) % p = (a%p - b%p) %p (√)
(a * b) % p = (a%p * b%p) %p (√)
(a / b) % p = (a%p / b%p) %p (×)
这里不难看出来做除法取余是错的吧,看个例子:
(100/50)%20 = 2 ≠ (100%20) / (50%20) %20 = 0
对于一些题目,由于数字太大,电脑存不下,我们必须在中间过程中进行求余。若这个算式中出现除法,我们就不能先做除法再取模,由上面可知“除法取余是错的”,由此我们就需要用逆元来代替。
例题:E-排列计数_第20届上海大学程序设计联赛夏季赛(校外同步赛) (nowcoder.com)
题目描述
输入描述:
输出描述:
输出一行一个整数,表示满足条件的排列数,由于答案可能很大,请对1e9+7取模
示例1
输入
1
输出
1
示例2
输入
3
输出
360
由题目可以看出来,我们需要求的是2*n!/2的值输出。
如果直接写阶乘取模输出,当然会wa咯。
这里稍微把那个除2的运算改成乘上2(模mod)的逆元再取模就会ac了。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//快速幂模板
int qmi(int a,int k,int p)
{
int res=1;
while(k)
{
if(k&1) res=(ll)res*a%p;
k>>=1;
a=(ll) a*a%p;
}
return res;
}
int main()
{
IOS;
ll n;
cin>>n;
ll ans=1;
for(int i=1;i<=2*n;i++)
ans=(ans*i)%mod;
cout<<ans*qmi(2,mod-2,mod)%mod<<endl;
return 0;
}
边栏推荐
- Helm deploy etcd cluster
- How are you in the first half of the year occupied by the epidemic| Mid 2022 summary
- Reptiles have a good time. Are you full? These three bottom lines must not be touched!
- Certains marchés de l'emploi de Shanghai refusent d'embaucher des personnes qui se rétablissent positives à Xinguan
- Qlabel marquee text display
- 视频化全链路智能上云?一文详解什么是阿里云视频云「智能媒体生产」
- 基于ppg和fft神经网络的光学血压估计【翻译】
- When visual studio code starts, it prompts "the code installation seems to be corrupt. Please reinstall." Solution to displaying "unsupported" information in the title bar
- AcWing 3537. Tree lookup complete binary tree
- Binary search tree
猜你喜欢
安装Mysql报错:Could not create or access the registry key needed for the...
Noninvasive and cuff free blood pressure measurement for telemedicine [translation]
Multithreading Basics: basic concepts of threads and creation of threads
Based on butterfly species recognition
Describe the process of key exchange
三年Android开发,2022疫情期间八家大厂的Android面试经历和真题整理
openmv4 学习笔记1----一键下载、图像处理背景知识、LAB亮度-对比度
AIRIOT物联网平台赋能集装箱行业构建【焊接工位信息监控系统】
pytorch常见损失函数
php+redis实现超时取消订单功能
随机推荐
RedisSystemException:WRONGTYPE Operation against a key holding the wrong kind of value
Countdown 2 days | live broadcast preview of Tencent cloud message queue data import platform
Human bone point detection: top-down (part of the theory)
R language ggplot2 visualization: use ggviolin function of ggpubr package to visualize violin diagram
Php+redis realizes the function of canceling orders over time
About static type, dynamic type, ID, instancetype
R语言ggplot2可视化:使用ggpubr包的ggstripchart函数可视化分组点状条带图(dot strip plot)、设置add参数为不同水平点状条带图添加箱图
Optical blood pressure estimation based on PPG and FFT neural network [translation]
根据PPG估算血压利用频谱谱-时间深度神经网络【翻】
Lucun smart sprint technology innovation board: annual revenue of 400million, proposed to raise 700million
关于静态类型、动态类型、id、instancetype
Graffiti intelligence is listed on the dual main board in Hong Kong: market value of 11.2 billion Hong Kong, with an annual revenue of 300 million US dollars
Digital "new" operation and maintenance of energy industry
Wx applet learning notes day01
First day of rhcsa study
Nuc11 cheetah Canyon setting U disk startup
青龙面板最近的库
Penetration test information collection - basic enterprise information
R语言ggplot2可视化:使用ggpubr包的ggviolin函数可视化小提琴图
Penetration test information collection - App information