首页 > 同余方程
开通博客写题解
头像 Rain_Fly
发表于 2024-03-27 11:25:04
求关于x的同余方程ax≡1(modb)的最小正整数解。 用拓展欧几里得定理求解即可，证明参考：https://zhuanlan.zhihu.com/p/103410252 代码： #include<bits/stdc++.h> typedef long&nb 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 louhc
发表于 2019-08-20 17:00:31
思路 简单的逆元入门题.如果是质数,直接用费马小定理求解即可.这里不一定是质数,所以要用.设存在整数使得.那么很明显.因此只要解出即可.直接用求出一组可行解,对取模即可.这里保证有解,因此不用判断是否为.复杂度为,也就是的复杂度. 代码 #include<bits/stdc++.h> u 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”