【中国剩余定理/扩展欧几里得定理】AcWing204.表达整数的奇怪方式——题解顺带中国剩余定理模板
2022/6/12 23:20:43
本文主要是介绍【中国剩余定理/扩展欧几里得定理】AcWing204.表达整数的奇怪方式——题解顺带中国剩余定理模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AcWing204.表达整数的奇怪方式
题解
模板
根据题目变形
#include <iostream> using namespace std; typedef long long LL; LL exgcd(LL a, LL b, LL &x, LL &y) { if(!b) { x = 1, y = 0; return a; } LL d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int main() { int n; cin >> n; LL m1, a1, x; cin >> m1 >> a1; for(int i = 0; i < n - 1; ++i) { LL m2, a2, k1, k2; cin >> m2 >> a2; LL d = exgcd(m1, m2, k1, k2); if( (a2 - a1) % d ) { x = -1; break; } k1 *= (a2 - a1) / d; k1 = (k1 % (m2 / d) + m2/d) % (m2 / d); //另k1最小使得a最小才能出现最小x a1 = k1 * m1 + a1; m1 = m1 / d * m2; } if(x != -1) x = (a1 % m1 + m1) % m1; cout << x << endl; return 0; }
这篇关于【中国剩余定理/扩展欧几里得定理】AcWing204.表达整数的奇怪方式——题解顺带中国剩余定理模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望