当前位置:网站首页>快速幂,逆元的求解
快速幂,逆元的求解
2022-08-11 07:49:00 【疯疯癫癫才自由】
875. 快速幂
给定 n
组 ai,bi,pi,对于每组数据,求出 abiimodpi
的值。
输入格式
第一行包含整数 n
。
接下来 n
行,每行包含三个整数 ai,bi,pi
。
输出格式
对于每组数据,输出一个结果,表示 abiimodpi
的值。
每个结果占一行。
数据范围
1≤n≤100000
,
1≤ai,bi,pi≤2×109
输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
1)迭代写法求快速幂
/**
* 1)迭代写法求快速幂
*/
#include <iostream>
using namespace std;
typedef long long LL;
int qmi(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1)
res=res*(LL)a%p;
b >>=1;
a=(LL)a*a%p;
}
return res;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int a,b,p;
cin >> a >> b >> p;
cout << qmi(a,b,p) << endl;
}
return 0;
}
2)递归求快速幂
/**
* 2)递归求快速幂
*/
#include <iostream>
using namespace std;
typedef long long LL;
int qmi(int a,int b,int p)
{
if(b==0)
return 1;
if(b&1)
return (LL)a*qmi(a,b-1,p)%p; //注意这里需要强制转换一下,int会溢出
else
{
LL temp=qmi(a,b/2,p);
return temp*temp%p;
}
}
int main()
{
int n;
cin >> n;
while(n--)
{
int a,b,p;
cin >> a >> b >> p;
cout << qmi(a,b,p) << endl;
}
return 0;
}
876. 快速幂求逆元
给定 n
组 ai,pi,其中 pi 是质数,求 ai 模 pi
的乘法逆元,若逆元不存在则输出 impossible
。
注意:请返回在 0∼p−1
之间的逆元。
乘法逆元的定义
若整数 b,m
互质,并且对于任意的整数 a,如果满足 b|a,则存在一个整数 x,使得 a/b≡a×x(modm),则称 x 为 b 的模 m 乘法逆元,记为 b−1(modm)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时,bm−2 即为 b
的乘法逆元。
输入格式
第一行包含整数 n
。
接下来 n
行,每行包含一个数组 ai,pi,数据保证 pi
是质数。
输出格式
输出共 n
行,每组数据输出一个结果,每个结果占一行。
若 ai
模 pi
的乘法逆元存在,则输出一个整数,表示逆元,否则输出 impossible
。
数据范围
1≤n≤105
,
1≤ai,pi≤2∗109
输入样例:
3
4 3
8 5
6 3
输出样例:
1
2
impossible
* 假设 a,b,m都是整数,m>1,且ab与1模m同余,则a与b互为模m的逆元。
* 所以当m为质数的时候,a的m-2次方就是a模m的逆元。(费马小定理)。
/**
* 假设 a,b,m都是整数,m>1,且ab与1模m同余,则a与b互为模m的逆元。
* 所以当m为质数的时候,a的m-2次方就是a模m的逆元。(费马小定理)。
*/
#include <iostream>
using namespace std;
typedef long long LL;
int qmi(int a,int b,int p)
{
if(b==0)
return 1;
if(b&1)
return (LL)a*qmi(a,b-1,p)%p; //注意这里需要强制转换一下,int会溢出
else
{
LL temp=qmi(a,b/2,p);
return temp*temp%p;
}
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int a,p;
cin >> a >> p;
if(a%p==0)
cout << "impossible\n";
else
cout << qmi(a,p-2,p) << endl;
}
return 0;
}
边栏推荐
- 囍楽cloud task source code
- 几何EX3 功夫牛宣布停售,入门级纯电产品为何总成弃子
- 1081 检查密码 (15 分)
- klayout--导出版图为gds文件
- 3.2 - classification - Logistic regression
- 分布式锁-Redission - 缓存一致性解决
- 【415. 字符串相加】
- Analysys and the Alliance of Small and Medium Banks jointly released the Hainan Digital Economy Index, so stay tuned!
- CSDN21天学习挑战赛——封装(06)
- Machine Learning Summary (2)
猜你喜欢
Project 1 - PM2.5 Forecast
About # SQL problem: how to set the following data by commas into multiple lines, in the form of column display
关于Excel实现分组求和最全文档
TF通过feature与label生成(特征,标签)集合,tf.data.Dataset.from_tensor_slices
通过记账,了解当月收支情况
Redis source code: how to view the Redis source code, the order of viewing the Redis source code, the sequence of the source code from the external data structure of Redis to the internal data structu
Write a resume like this, easy to get the interviewer
1003 我要通过 (20 分)
年薪40W测试工程师成长之路,你在哪个阶段?
[C语言] sscanf如何实现sscanf_s?
随机推荐
【LeetCode】链表题解汇总
1056 Sum of Combinations (15 points)
tf.reduce_mean() and tf.reduce_sum()
1081 检查密码 (15 分)
TF中的四则运算
Activity的四种启动模式
抽象类和接口
1002 Write the number (20 points)
1101 How many times B is A (15 points)
Serverless + domain name can also build a personal blog? Really, and soon
oracle数据库中列转行,列会有变化
1076 Wifi密码 (15 分)
零基础SQL教程: 基础查询 05
Keep track of your monthly income and expenses through bookkeeping
C语言-结构体
The most complete documentation on Excel's implementation of grouped summation
go sqlx 包
Tensorflow中使用tf.argmax返回张量沿指定维度最大值的索引
接口测试的基础流程和用例设计方法你知道吗?
CSDN21天学习挑战赛——封装(06)