經典算法 (A/B) mod C

(A/B) mod C

問題描述

求(A/B)%C,但由于A和B實在太大了,我們只給出A % C,B % C。

(我們保證給定的A必能被B整除,且gcd(B,C) = 1)。

輸入描述

輸入一行三個整數,分別是A % C,B % C,C。

輸出描述

輸出(A/B)%C的值。

輸入示例1

22 11 49

輸出示例1

2

樣例解釋

(6000 / 60) % 49 = 2
60與49最大公約數為1,
6000%49 = 22,60 % 49 = 11
輸入22 11 49
輸出2

輸入示例2

1000 53 9973

輸出示例2

7922

輸入示例3

87 1022 9973

輸出示例3

6060

c++代碼(拓展歐幾里得算法 通用法,也就是C可以為任意實數)

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll A, B, C;ll extend_gcd(ll a, ll b, ll &x, ll &y) {//返回d = gcd(a, b),并且找到ax + by = d的一個特解x,y。if (b == 0) { x = 1, y = 0; return a; }ll d = extend_gcd(b, a % b, y, x);y -= a / b * x;return d;
}ll mod_inverse(ll B, ll C) {//返回B mod C的逆ll x, y;extend_gcd(B, C, x, y);//x可能是負數return (x % C + C) % C;
}int main() {cin >> A >> B >> C;cout << (A * mod_inverse(B, C)) % C;return 0;
}//by wqs

c++代碼(特別地,當C為質數的時候,可以使用費馬小定理,不是通用法)

#include<bits/stdc++.h>using namespace std;typedef long long ll;ll A, B, C;ll fastPow(ll a, ll b, ll mod) {if (b == 0) return 1 % mod;if (b == 1) return a % mod;ll k = fastPow(a, b / 2, mod);if (b % 2 == 0) return (k * k) % mod;else return (((k * k) % mod) * a) % mod;
}ll mod_inverse(ll B, ll C) { return fastPow(B, C - 2, C); }int main() {cin >> A >> B >> C;//前提C為質數cout << (A * mod_inverse(B, C)) % C;return 0;
}//by wqs

題目解析

之所以要求gcd(B,C) = 1,是因為gcd(B,C) != 1的時候會有多個答案,這是硬性要求,否則題目無解。

然后我們要對C分類討論。

如果C是質數,一般使用費馬小定理。

如果C不是質數,一般使用通用法拓展歐幾里得算法。

一般涉及到除法取模,模值都是質數,費馬小定理用的更多。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/80120.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/80120.shtml
英文地址,請注明出處:http://en.pswp.cn/web/80120.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

大數據技術的主要方向及其應用詳解

文章目錄 一、大數據技術概述二、大數據存儲與管理方向1. 分布式文件系統2. NoSQL數據庫3. 數據倉庫技術 三、大數據處理與分析方向1. 批處理技術2. 流處理技術3. 交互式分析4. 圖計算技術 四、大數據機器學習方向1. 分布式機器學習2. 深度學習平臺3. 自動機器學習(AutoML) 五、…

Deeper and Wider Siamese Networks for Real-Time Visual Tracking

現象&#xff1a; the backbone networks used in Siamese trackers are relatively shallow, such as AlexNet , which does not fully take advantage of the capability of modern deep neural networks. direct replacement of backbones with existing powerful archite…

ubuntu22.04卸載vscode

方法 1&#xff1a;通過 Snap 卸載 VSCode 如果你是通過 Snap 安裝的 VSCode&#xff08;Ubuntu 22.04 默認推薦方式&#xff09;&#xff0c;按照以下步驟卸載&#xff1a; 檢查是否通過 Snap 安裝&#xff1a; bash snap list | grep code如果輸出顯示 code&#xff0c;說明…

OpenCV 背景建模詳解:從原理到實戰

在計算機視覺領域&#xff0c;背景建模是一項基礎且重要的技術&#xff0c;它能夠從視頻流中分離出前景目標&#xff0c;廣泛應用于運動目標檢測、視頻監控、人機交互等場景。OpenCV 作為計算機視覺領域最受歡迎的開源庫之一&#xff0c;提供了多種高效的背景建模算法。本文將深…

Android native崩潰問題分析

最近在做NDK項目的時候&#xff0c;出現了啟動應用就崩潰了&#xff0c;崩潰日志如下&#xff1a; 10:41:04.743 A Build fingerprint: samsung/g0qzcx/g0q:13/TP1A.220624.014/S9060ZCU4CWH1:user/release-keys 10:41:04.743 A Revision: 12 10:41:04.743 A ABI: arm64…

【Shell的基本操作】

文章目錄 一、實驗目的二、實驗環境三、實驗內容3.1 Shell變量與腳本基礎3.2 定制終端提示符&#xff08;PS1變量&#xff09;3.3 文件查找與類型確認&#xff08;find命令&#xff09;3.4 管道命令實戰&#xff08;用戶登錄統計&#xff09;3.5 交互式備份壓縮腳本 四、總結4.…

快速選擇算法:優化大數據中的 Top-K 問題

在處理海量數據時&#xff0c;經常會遇到這樣的需求&#xff1a;找出數據中最大的前 K 個數&#xff0c;而不必對整個數據集進行排序。這種場景下&#xff0c;快速選擇算法&#xff08;Quickselect&#xff09;就成了一個非常高效的解決方案。本文將通過一個 C 實現的快速選擇算…

AQS 基本思想與源碼分析

充分了解 AbstractQueuedSynchronizer 對于深入理解并發編程是有益處的&#xff0c;它是用來構建鎖或者其他同步組件的基礎框架&#xff0c;我們常用的同步工具類如 CountDownLatch、Semaphore、ThreadPoolExecutor、ReentrantLock 和 ReentrantReadWriteLock 內部都用到了它。…

理解位圖算法:使用 C++ 實現高效數據查重

在處理海量數據時&#xff0c;我們常常需要檢查某個元素是否已經存在于集合中。傳統的方法如哈希表或集合容器雖然有效&#xff0c;但在數據量極大的情況下會占用大量內存。這時&#xff0c;位圖算法 (Bitmap) 就成為了一種非常高效的解決方案。本文將通過分析一段使用位圖算法…

數學復習筆記 12

前言 現在做一下例題和練習題。矩陣的秩和線性相關。另外還要復盤前面高數的部分的內容。奧&#xff0c;之前矩陣的例題和練習題&#xff0c;也沒有做完&#xff0c;行列式的例題和練習題也沒有做完。累加起來了。以后還是得學一個知識點就做一個部分的內容&#xff0c;日拱一…

1-10 目錄樹

在ZIP歸檔文件中&#xff0c;保留著所有壓縮文件和目錄的相對路徑和名稱。當使用WinZIP等GUI軟件打開ZIP歸檔文件時&#xff0c;可以從這些信息中重建目錄的樹狀結構。請編寫程序實現目錄的樹狀結構的重建工作。 輸入格式: 輸入首先給出正整數N&#xff08;≤104&#xff09;…

Python爬蟲實戰:研究 RPC 遠程調用機制,實現逆向解密

1. 引言 在網絡爬蟲技術的實際應用中,目標網站通常采用各種加密手段保護其數據傳輸和業務邏輯。這些加密機制給爬蟲開發帶來了巨大挑戰,傳統的爬蟲技術往往難以應對復雜的加密算法。逆向解密作為一種應對策略,旨在通過分析和破解目標網站的加密機制,獲取原始數據。 然而,…

debugfs:Linux 內核調試的利器

目錄 一、什么是 debugfs&#xff1f;二、debugfs 的配置和啟用方式2.1 內核配置選項2.2 掛載 debugfs2.3 Android 系統中的 debugfs 三、debugfs 的典型應用場景3.1 調試驅動開發3.2 內核子系統調試3.3 性能分析 四、常見 debugfs 子目錄與功能示例4.1 /sys/kernel/debug/trac…

lua 作為嵌入式設備的配置語言

從lua的腳本中獲取數據 lua中棧的索引 3 | -1 2 | -2 1 | -3 可以在lua的解釋器中加入自己自定的一些功能,其實沒啥必要,就是為了可以練習下lua

棋牌室臺球室快速接入美團團購接口

北極星平臺從2024年12月份開始慢慢關閉&#xff0c;現在很多開發者反饋北極星token已經不能刷新了&#xff0c;全部遷移到美團團購綜合平臺。 申請這個平臺要求很高 1、保證金費用要15萬起步 2、平臺必須是二級等保和安全產品 &#xff0c;一個二級等保費用10萬起步 所以很多…

開源輕量級地圖解決方案leaflet

Leaflet 地圖&#xff1a;開源輕量級地圖解決方案 Leaflet 是一個開源的 JavaScript 庫&#xff0c;用于在網頁中嵌入交互式地圖。它以輕量級、靈活性和易用性著稱&#xff0c;適用于需要快速集成地圖功能的項目。以下是關于 Leaflet 的詳細介紹和使用指南。 1. Leaflet 的核心…

一個批量文件Dos2Unix程序(Microsoft Store,開源)1.1.0 編碼檢測和預覽

之前的版本是個意思意思&#xff0c;驗證商店發布的&#xff08;其實是我以前自己用的工具&#xff09;&#xff0c;這次把格式檢查和轉換都做上了&#xff0c;功能應該差不多了&#xff0c;還有一些需要小改進的地方。 因為還沒什么用戶嘛&#xff0c;還是保持全功能免費試用。…

特征提取:如何從不同模態中獲取有效信息?

在多模態學習中&#xff0c;不同模態&#xff08;文本、圖像、語音、視頻、傳感器數據等&#xff09;所攜帶的信息豐富且互補。但不同模態的數據結構、表示空間、時空分布截然不同&#xff0c;因此&#xff0c;如何對各模態進行高效、有效的特征提取&#xff0c;是整個多模態學…

Go語言爬蟲系列教程 實戰項目JS逆向實現CSDN文章導出教程

爬蟲實戰&#xff1a;JS逆向實現CSDN文章導出教程 在這篇教程中&#xff0c;我將帶領大家實現一個實用的爬蟲項目&#xff1a;導出你在CSDN上發布的所有文章。通過分析CSDN的API請求簽名機制&#xff0c;我們將繞過平臺限制&#xff0c;獲取自己的所有文章內容&#xff0c;并以…

交叉熵損失函數,KL散度, Focal loss

交叉熵損失函數&#xff08;Cross-Entropy Loss&#xff09; 交叉熵損失函數&#xff0c;涉及兩個概念&#xff0c;一個是損失函數&#xff0c;一個是交叉熵。 首先&#xff0c;對于損失函數。在機器學習中&#xff0c;損失函數就是用來衡量我們模型的預測結果與真實結果之間…