【~~~】POJ-1006

很簡單的一道題目,但是引出了很多知識點。

這是一道中國剩余問題,先貼一下1006的代碼。

#include "stdio.h"

#define MAX 21252

int main()

{

?

? ? int p , e , i , d , n = 1 , days = 0;

?

? ? while(1)

? ? {

? ? ? ? scanf("%d %d %d %d",&p,&e,&i,&d);

?

? ? ? ? if( p == -1 && e == -1 && i == -1 && d == -1)

? ? ? ? ? ? break;

?

? ? ? ? days = (/*28*33*gcd1(28*33,23)*/5544 * p + /*23*33*gcd1(23*33,28)*/14421 * e + /*23*28*gcd1(23*28,33)*/1288 * i + MAX - d)% MAX ;

?

? ? ? ? if(days == 0)

? ? ? ? ? ? days = MAX ;

?

? ? ? ? printf("Case %d: the next triple peak occurs in %d days.\n",n,days);

?

? ? ? ? n++;

?

? ? }

? ? return 1;

}

?

?

乘法逆元的求解方式

?

  Extended Euclid (d,f) //算法求d關于模f的乘法逆元d-1 ,即 d* d-1 mod f = 1

  1 。(X1,X2,X3) := (1,0,f); (Y1,Y2,Y3) := (0,1,d)

  2。 if (Y3=0) then return d-1 = null //無逆元

  3。 if (Y3=1) then return d-1 = Y2 //Y2為逆元

  4。 Q := X3 div Y3 //整除

  5。 (T1,T2,T3) := (X1 - Q*Y1,X2 - Q*Y2,X3 - Q*Y3)

  6 。(X1,X2,X3) := (Y1,Y2,Y3)

  7。 (Y1,Y2,Y3) := (T1,T2,T3)

  8。 goto 2


code:

#include "stdio.h"

?

long gcd1(long a, long p) ? ?//求a關于p的逆元,歐幾里德算法

{

? ? long c , d = a;

? ? long q0 = 0 , q1 = 1 , q2;

? ? do{

? ? ? ? c = a%p;

? ? ? ? if(c)

? ? ? ? q2 = -1*a/p*q1+q0;

? ? ? ? q0 = q1;

? ? ? ? q1 = q2;

? ? ? ? a = p;

? ? ? ? p = c;

? ? ? ? }while(c);

? ? ? ? return q2>0?q2:q2+d;

}

?

int main()

{

? ? long a,b,i;

? ? while(1)

? ? {

? ? ? ? scanf("%d%d", &a, &b);

? ? ? ? if (a==0 && b==0)

? ? ? ? ? ? break;

? ? ? ? printf("%d\n",gcd1(b,a));

? ? }

}

?

窮舉的方式求逆元:

code:

#include "stdio.h"

?

?

long int gcd( long int a , long int p );

?

?

?

?

int main() ? ? ? ?//求a關于p的逆元,a關于p的逆元在(1,p-1)之中 ? 所以用窮舉的方法來求解

{

? ? long int interver;

? ? interver = gcd( 35 , 3 );

?

? ? printf("%ld",interver);

?

? ? return 1 ;

}

?

?

long int gcd( long int a , long int p )

{

?

? ? long int interver = 0 , j;

?

? ? for( j = 0 ; j < p ; j++ )

? ? {

? ? ? ? if( (a * j)%p == 1 )

? ? ? ? ? ? {

? ? ? ? ? ? ? ? interver = j;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? }

? ? }

?

? ? return interver;

}

轉載于:https://www.cnblogs.com/zuckerTT/archive/2011/09/25/2189862.html

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

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

相關文章

Java快速掃盲指南

文章轉自&#xff1a;https://segmentfault.com/a/1190000004817465#articleHeader22 JDK&#xff0c;JRE和 JVM 的區別 JVM&#xff1a;java 虛擬機&#xff0c;負責將編譯產生的字節碼轉換為特定機器代碼&#xff0c;實現一次編譯多處執行&#xff1b; JRE&#xff1a;java運…

xcode擴展_如何將Xcode插件轉換為Xcode擴展名

xcode擴展by Khoa Pham通過Khoa Pham 如何將Xcode插件轉換為Xcode擴展名 (How to convert your Xcode plugins to Xcode extensions) Xcode is an indispensable IDE for iOS and macOS developers. From the early days, the ability to build and install custom plugins ha…

leetcode 861. 翻轉矩陣后的得分(貪心算法)

有一個二維矩陣 A 其中每個元素的值為 0 或 1 。 移動是指選擇任一行或列&#xff0c;并轉換該行或列中的每一個值&#xff1a;將所有 0 都更改為 1&#xff0c;將所有 1 都更改為 0。 在做出任意次數的移動后&#xff0c;將該矩陣的每一行都按照二進制數來解釋&#xff0c;矩…

數據分析團隊的價值_您的數據科學團隊的價值

數據分析團隊的價值This is the first article in a 2-part series!!這是分兩部分的系列文章中的第一篇&#xff01; 組織數據科學 (Organisational Data Science) Few would argue against the importance of data in today’s highly competitive corporate world. The tech…

mysql 保留5位小數_小猿圈分享-MySQL保留幾位小數的4種方法

今天小猿圈給大家分享的是MySQL使用中4種保留小數的方法&#xff0c;希望可以幫助到大家&#xff0c;讓大家的工作更加方便。1 round(x,d)用于數據x的四舍五入, round(x) ,其實就是round(x,0),也就是默認d為0&#xff1b;這里有個值得注意的地方是&#xff0c;d可以是負數&…

leetcode 842. 將數組拆分成斐波那契序列(回溯算法)

給定一個數字字符串 S&#xff0c;比如 S “123456579”&#xff0c;我們可以將它分成斐波那契式的序列 [123, 456, 579]。 形式上&#xff0c;斐波那契式序列是一個非負整數列表 F&#xff0c;且滿足&#xff1a; 0 < F[i] < 2^31 - 1&#xff0c;&#xff08;也就是…

博主簡介

面向各層次&#xff08;從中學到博士&#xff09;提供GIS和Python GIS案例實驗實習培訓&#xff0c;以解決問題為導向&#xff0c;以項目實戰為主線&#xff0c;以科學研究為思維&#xff0c;不講概念&#xff0c;不局限理論&#xff0c;簡單照做&#xff0c;即學即會。 研究背…

自定義Toast 很簡單就可以達到一些對話框的效果 使用起來很方便

自定義一個layout布局 通過toast.setView 設置布局彈出一些警示框 等一些不會改變的提示框 很方便public class CustomToast {public static void showUSBToast(Context context) {//加載Toast布局 View toastRoot LayoutInflater.from(context).inflate(R.layout.toas…

微信小程序阻止冒泡點擊_微信小程序bindtap事件與冒泡阻止詳解

bindtap就是點擊事件在.wxml文件綁定:cilck here在一個組件的屬性上添加bindtap并賦予一個值(一個函數名)當點擊該組件時, 會觸發相應的函數執行在后臺.js文件中定義tapMessage函數://index.jsPage({data: {mo: Hello World!!,userid : 1234,},// 定義函數tapMessage: function…

同情機器人_同情心如何幫助您建立更好的工作文化

同情機器人Empathy is one of those things that can help in any part of life whether it’s your family, friends, that special person and even also at work. Understanding what empathy is and how it effects people took me long time. I struggle with human inter…

數據庫課程設計結論_結論

數據庫課程設計結論When writing about learning or breaking into data science, I always advise building projects.在撰寫有關學習或涉足數據科學的文章時&#xff0c;我總是建議構建項目。 It is the best way to learn as well as showcase your skills.這是學習和展示技…

mongo基本使用方法

mongo與關系型數據庫的概念對比&#xff0c;區分大小寫&#xff0c;_id為主鍵。 1.數據庫操作 >show dbs #查看所有數據庫 >use dbname #創建和切換數據庫&#xff08;如果dbname存在則切換到該數據庫&#xff0c;不存在則創建并切換到該數據庫&#xff1b;新創建的…

leetcode 62. 不同路徑(dp)

一個機器人位于一個 m x n 網格的左上角 &#xff08;起始點在下圖中標記為“Start” &#xff09;。 機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角&#xff08;在下圖中標記為“Finish”&#xff09;。 問總共有多少條不同的路徑&#xff1f; 例如&…

第一名數據科學工作冠狀病毒醫生

背景 (Background) 3 years ago, I had just finished medical school and started working full-time as a doctor in the UK’s National Health Service (NHS). Now, I work full-time as a data scientist at dunnhumby, writing code for “Big Data” analytics with Pyt…

mysql時間區間效率_對于sql中使用to_timestamp判斷時間區間和不使用的效率對比及結論...

關于日期函數TO_TIMESTAMP拓展&#xff1a;date類型是Oracle常用的日期型變量&#xff0c;時間間隔是秒。兩個日期型相減得到是兩個時間的間隔&#xff0c;注意單位是“天”。timestamp是DATE類型的擴展&#xff0c;可以精確到小數秒(fractional_seconds_precision)&#xff0c…

ajax 賦值return

ajax 獲得結果后賦值無法成功&#xff0c; function grades(num){ var name"";   $.ajax({    type:"get",     url:"",     async:true,     success:function(result){     var grades result.grades;     …

JavaScript(ES6)傳播算子和rest參數簡介

by Joanna Gaudyn喬安娜高登(Joanna Gaudyn) JavaScript(ES6)傳播算子和rest參數簡介 (An intro to the spread operator and rest parameter in JavaScript (ES6)) 擴展運算符和rest參數都被寫為三個連續的點(…)。 他們還有其他共同點嗎&#xff1f; (Both the spread opera…

python爬蟲消費者與生產者_Condition版生產者與消費者模式

概述&#xff1a;在人工智能來臨的今天&#xff0c;數據顯得格外重要。在互聯網的浩瀚大海洋中&#xff0c;隱藏著無窮的數據和信息。因此學習網絡爬蟲是在今天立足的一項必備技能。本路線專門針對想要從事Python網絡爬蟲的同學而準備的&#xff0c;并且是嚴格按照企業的標準定…

【Python包】安裝teradatasql提示找不到pycryptodome模塊錯誤(pycrypto,pycryptodome和crypto加密庫)...

1.問題描述 安裝teradatasql時&#xff0c;出現錯誤Could not find a version that satisfies the requirement pycryptodome&#xff0c;具體如下&#xff1a; 2.解決方法 查看Python第三方庫目錄$PYTHON_HOME/lib/python3.6/site-packages目錄下沒有pycryptodome目錄&#xf…

leetcode 860. 檸檬水找零(貪心算法)

在檸檬水攤上&#xff0c;每一杯檸檬水的售價為 5 美元。 顧客排隊購買你的產品&#xff0c;&#xff08;按賬單 bills 支付的順序&#xff09;一次購買一杯。 每位顧客只買一杯檸檬水&#xff0c;然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零&#xff0…