跳到主要內容

UVa 106 Fermat vs. Pythagoras

解題策略:

勾股定理 A2+B2=C2,或者叫做畢氏定理,符合公式的數對(A,B,C)就叫一組勾股數 (畢氏三元數)。

題目給一個正整數N,要我們找出兩個答案,第一: 0~N之間總共有幾組互質勾股數? 第二: 0~N之間有幾個數完全不屬於任何一組勾股數? 我舉個例子N=10,那麼0~10之間可以找到兩組勾股數(3,4,5)與(6,8,10),其中只有(3,4,5)一組互質,所以第一個答案是1。再來,3,4,5,6,8,10 都屬於某一組勾股數,完全沒用到的數字是1,2,7,9,共四個數,所以第二個答案是4。

解題關鍵在於如何快速找出一堆勾股數。我想就別折騰了,要解這題就要知道勾股數的通解,單純用暴力搜尋鐵定超時。

維基百科的勾股數條目參考來的通解:
給一個任意數對(X,Y),用以下公式代
A = X2 - Y2
B = 2XY
C = X2 + Y2
得出的A,B,C就是一組勾股數。

若 (X,Y) 恰好互質而且一奇一偶,那麼會得到一組(A,B,C)互質的勾股數。
知道通解後,雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。

找出不屬於勾股數的數字,直接開一個 size=1000000 的陣列來記錄所有出現過的數字 (用array或是bitset都成)。別忘了一點,我們上面只列出互質的勾股數,但是勾股數的任意整數倍也都是勾股數,如(3,4,5) (6,8,10) (9,12,15),這些數字也都必須列入紀錄。

閒聊

我知道Fermat是費瑪,不過標題看很久才發現P先生是畢達哥拉斯orz,對於世界第一的先生(Runtime 0.008秒 by Java),感到由衷的敬佩。

留言

  1. hello,台湾同胞你好,UVA刷了多少题了?

    回覆刪除
  2. 這題有個蠻 tricky 的地方 , 就是您程式碼的 index 部分用的是1000

    // 用雙層迴圈跑遍(x,y)所有可能的值
    for (int x=1; x<1000; ++x){

    如果傻傻的用最大值 1000000 代入 , 還是會超過時間QQ

    回覆刪除
  3. 請問 再快 就只能建表了嗎?

    回覆刪除
    回覆
    1. 其實我不知道該怎麼更快,你可以試試看建表,不知道建表能不能達到0.008秒XD

      刪除
    2. http://zerojudge.tw/ShowProblem?problemid=a247
      被測資打敗了...

      刪除
    3. 原來現在ZJ也有這題了,今天晚上來挑戰一下XD

      刪除

張貼留言

這個網誌中的熱門文章

讀書心得: 撒哈拉的故事

初拿起「撒哈拉的故事」時,我心中想著大概是本以沙漠為背景的美麗幻想般的愛情小說吧,有誰會真的費盡千辛萬苦跑去撒哈拉沙漠,在物質極為缺乏的環境下過著刻苦的生活呢? 沒想到這人就是三毛,只因為一個理由「我要認識沙漠」。

「撒哈拉的故事」是三毛與她的丈夫荷西在撒哈拉沙漠旅遊生活的紀實,生活在沙漠很糟糕,至少我看完最後一篇『白手成家』後認為實在很糟,不過在樂觀又開朗的三毛的筆下,撒哈拉沙漠化為一個有趣又不可思議的國度,說著一個又一個異國的故事。

如果不是三毛,我無法想像原來世界上還有這樣子的一群人,還有這等事情,你能想像沙哈拉威人三四年才洗一次澡嗎? 『觀浴記』裡三毛跑去看沙漠女人洗澡,要先用蒸氣蒸,再用石片刮下身上的泥沙,而且沙漠女人不只洗外面,還洗裡面,讓我看的哈哈大笑。『娃娃新娘』 裡則是三毛的一個沙哈拉威鄰居叫「姑卡」要出嫁了,可是她才十歲呀,結婚習俗更是特別,新郎去迎接新娘時,新娘拼命的抵抗,原來才在沙哈拉威人的觀念裡,打得激烈才叫做「好女人」,不掙扎事後會被取笑的。

沙哈拉威人很少受教育,思想沒有邏輯,通常講道理是講不通的。有次三毛要參加晚宴,遍尋不著自己的漂亮高跟鞋,反倒是鞋櫃上多了一雙破鞋子,原來高跟鞋被鄰居小女孩偷去穿了。事後三毛很生氣地跟她理論,小女孩竟然回嘴「生氣,生氣,你的鞋子在我家,我的鞋子還不是在你家,我比你還要氣。」聽見這種話真的是秀才遇到兵,有理講不清,還好三毛是個灑脫的人,笑笑就過去了。

事實上,生活在沙漠真的需要灑脫,老是計較小事肯定活不下去。除了講不清道理的沙拉哈威鄰居,沙漠也有許多危險,書中至少有兩次三毛差點在沙漠裡丟掉小命。但是每一篇故事裡,我都看見一位勇氣可嘉的中國女孩兒,她不屈不撓,以樂觀的心和智慧面對生活中的困難,盡情的玩,盡情的享受生活,像個瘋狂的孩子般,最後甚至布置了一個號稱撒哈拉沙漠裡最美麗的家,連記者都聞風專程前來拜訪,他們的物質生活雖不富裕,但是精神卻很富足。

說到三毛不能不提她的另一半荷西。三毛書裡這樣子描寫『荷西有一個很大的優點,任何三毛所做的事情,在別人看來也許是瘋狂的行為,在他看來卻是理所當然的』,所以當三毛說要去沙漠時,荷西早她兩個月,就先對著撒哈拉沙漠找工作去了,沙漠裡的瘋狂事也總有荷西的一份。人生能遇見這樣的他,既是羨慕,也是感動。

8. 使用視圖與相機鏡頭轉換,及 gluLookAt() - OpenGL FAQ

返回 OpenGL FAQ 目錄

8.010 OpenGL裡的相機鏡頭到底是怎麼運作的呢?  就目前的OpenGL來說,沒有相機鏡頭這種東西。更精確地講,相機永遠都位處於眼空間座標的原點 (0,0,0)。你的OpenGL應用程式為了假裝出移動相機的樣子,必須移動場景,對整個世界場景做相機鏡頭的逆空間轉換。

8.020 我要如何移動場景裡的眼睛或者相機鏡頭? 以相機鏡頭模型來說,OpenGL 並沒有提供介面去做這件事情。然而,GLU庫提供了gluLookAt()函數,傳入眼睛本身位置,眼睛瞄準點位置,以及朝上向量,都是世界空間坐標。這個函數依據參數計算出正確的相機逆空間轉換矩陣,並且乘上目前的矩陣。

8.030 我的相機鏡頭應該放在 ModelView 矩陣還是 Projection矩陣? GL_PROJECTION 矩陣只應該包含投影變換,它必須將眼空間坐標(eye space coordinates)轉換到裁切坐標(clip coordinates)。

GL_MODELVIEW矩陣呢,如其名,應該包含模型(modeling)與視圖(viewing)轉換,將物體空間坐標轉換成眼空間座標。所以請記住,永遠把相機鏡頭轉換放在GL_MODELVIEW矩陣,而不是GL_PROJECTION矩陣。

你可以把投影矩陣(projection matrix)想像成相機鏡頭的各種特性,像是視角的寬窄、焦距、用了魚眼鏡頭等等。而把模型視圖矩陣(model-view matrix)想成,你目前拿著相機站立的位置,及鏡頭指向的方向。

這份 The game dev FAQ 對這兩個矩陣說明得很不錯。

去讀讀 Steve Baker 的文章「濫用投影」(備用連結) 吧。此篇文章寫得很好,值得推薦。它曾經幫助過許多OpenGL新手程式員。

8.040 我該如何實現鏡頭變焦 (Zoom) 的操作? 簡單的做法是對 ModelView矩陣做等比縮放(uniform scale)。但是當模型放得太大時,通常會導致模型被近平面及遠平面裁切掉。一個比較好的做法是限縮投影矩陣裡view volume的寬與高。舉例來說,你的程式對應使用者的輸入,儲存了一個縮放參數值。當縮放值是1.0 時不變焦。縮放值變大就縮小視角,結果模型看起來就放大了。縮放值變小時就反過來做。程式碼範例看起來可能像這樣子:
/* 如果…

UVa 10018 Reverse and Add

解題策略這題是這樣的,要把輸入的數字反轉,例如1357變成7531,然後與原數相加。直到這個數字變成迴文(palindrome)為止,像是1357+7531=8888,8888就是一個迴文。本題只需要按照著要求計算即可,唯一比較技巧是反轉一個整數 int:reverse()
注意需要注意變數範圍:至少要 unsigned long 才能容納題目的數字範圍。而printf()、scanf() 與 unsigned long 打交道的代號是%lu。

爭議點這題有個爭議點是第一個數字到底需不需要判斷回文,舉個例子:
輸入2,那麼該輸出0 2或者1 4?舊版的UVa測資要求必須要輸出1 4,這有些不合常理,新版則是把爭議性測資都拿掉了,所以兩種寫法都能AC。但是在zerojudge.tw上就必須輸出1 4才行。

PS.這題我不小心把某個unsigned long打成int,抓了好久的bug。