COJ 1163 乘法逆元的求解
2024-10-21 05:53:26
乘法逆元就是求一个 a/b = c(mod m)在已知a%m , b%m 的条件下 求c的解
#include <cstdio>
#include <cstring> using namespace std;
#define ll long long
const int N = ;
int val[N]; ll ex_gcd(ll a , ll b , ll &x , ll &y)
{
if(b == ){
x= , y=;
return a;
}
ll ans = ex_gcd(b,a%b,x,y);
ll t=x;
x=y,y=t-a/b*y;
return ans;
} ll inv(ll a , ll b , ll mod)
{
ll x , y;
ll d = ex_gcd(b,mod,x,y);
return a*x%mod;
} int main()
{
int n,m;
while(scanf("%d%d" , &n , &m ) == )
{
ll sum = ;
for(int i= ; i<n ; i++){
scanf("%d" , val+i);
sum = (sum*val[i])%m;
}
for(int i= ; i<n ; i++){
ll ans = (inv(sum , (ll)val[i] , m)+m)%m;
if(i==) printf("%lld" , ans);
else printf(" %lld" , ans);
}
printf("\n");
}
return ;
}
最新文章
- [转]asp.net的ajax以及json
- Mysql增删改
- php特殊字符过滤,html标签处理
- Java中堆和栈的区别(转)
- jQuery练习一好友列表变色
- C#正则表达式Regex类
- C语言身份证信息查询系统(修改版)
- tomcat 插件
- 关于Response.redirect和Response.End出现线程中止异常的处理
- 浅谈Log4net在项目中如何记录日志
- 学习DButils笔记
- docker ,docker与虚拟机的区别
- 【PHPStorm使用手册】如何设置字体大小?
- 如何删除github里面的项目
- 贝尔数(来自维基百科)&; Stirling数
- JAVA获取文件夹下所有的文件
- scikit
- csharp:获取 DNS、网关、子网掩码、IP
- json和xml以及ajax的数据格式用法
- POJ 3017 DP + 单调队列 + 堆