国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 學(xué)院 > 開(kāi)發(fā)設(shè)計(jì) > 正文

拓展歐幾里得

2019-11-11 03:19:36
字體：大 中 小
來(lái)源：轉(zhuǎn)載
供稿：網(wǎng)友

輾轉(zhuǎn)相除法

int gcd(int a, int b){ return a == 0 ? b : gcd(b % a, a); }

拓展歐幾里得算法

ll exgcd(ll a, ll b){ if(b == 0) { x = 1, y = 0; return a; } else { ll ans = exgcd(b, a%b); ll tmp = x; x = y; y = tmp - (a / b) * x; return ans; }}

例題：同余方程 Mod

Noip2012提高組復(fù)賽Day2T1

描述

求關(guān)于x的同余方程ax ≡ 1 (mod b)的最小正整數(shù)解。

格式

輸入格式 輸入只有一行，包含兩個(gè)正整數(shù)a, b，用一個(gè)空格隔開(kāi)。 輸出格式 輸出只有一行，包含一個(gè)正整數(shù)x0，即最小正整數(shù)解。輸入數(shù)據(jù)保證一定有解。

樣例1

樣例輸入1

3 10

樣例輸出1

7

超裸的題，直接上拓展歐幾里得

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;typedef long long ll;int x, y;ll exgcd(ll a, ll b){ if(b == 0) { x = 1, y = 0; return a; } else { ll ans = exgcd(b, a%b); ll tmp = x; x = y; y = tmp - (a / b) * x; return ans; }}int main(){ ll a,b; cin>>a>>b; exgcd(a, b); x = (x + b) % b;//防止出現(xiàn)負(fù)數(shù) cout<<x; return 0;}

發(fā)表評(píng)論 共有條評(píng)論
用戶(hù)名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板： 靖州| 丹棱县| 明溪县| 太湖县| 连平县| 连平县| 湖口县| 维西| 威信县| 库车县| 册亨县| 阿拉善右旗| 科技| 积石山| 谢通门县| 大同县| 重庆市| 嘉义县| 玛曲县| 大理市| 广安市| 江都市| 东丰县| 宜兰县| 遵义市| 新余市| 保康县| 齐齐哈尔市| 广平县| 丰顺县| 宜兰市| 富裕县| 宣恩县| 姚安县| 黄平县| 通许县| 无锡市| 满洲里市| 右玉县| 曲周县| 绿春县|