瑞の資訊備忘錄

一、目的：在電腦科學中有小部份的領域是使用電腦來產生證明和協助驗證，首先四色問題的證明就是完全

            依靠電腦程式的協助來完成並且目前已經確認成功的將高階語言轉換至低階的晶片。

            這個問題的計算量與部份的費瑪最後定理相關：

                    根據上述定理，    ,當n>2 時沒有正整數解。

            (連結UVa online原文題庫)

二、問題說明：

     給一個正整數N, 寫一個程式計算右式的兩次方程式的解  一    

     這裡的x,y,z是限制正整數小於等於N，計算truple(x,y,z)的數量且x<y<z，並且它們是互質，

     (ie.,它們沒有共同的除算大於1)。並且另外計算0<p<=N的數量，這理的p不屬於任何truple

     的數值(不只是互質的truple)。 

三、輸入與輸出說明：

     輸入包含一系列的正整數，每行一個整數。每一個輸入檔的整數是小於或等於1000000。使用檔案

     結束符號表示輸入結束。在輸入檔案中的每個整數N輸出兩個整數並使用一個空白字元作為分隔。

     第一個整數是互質Truple的數量。(該truple的每個部份必須是小於等於N)。第二個整數是計算不屬

     於任何truple所包含的數值的數量，數值的範圍小於等於N。它們應該是每行輸入時就輸出一行。

     Ex：       Sample Input                              Sample Output

                  10                               =>                 1 4

                  25                               =>                 4 9

                  100                             =>                16 27 

四、演算法說明：

4-1、 該程式必須使用畢氏三元數的通式解，公式如下：

         x = | m^2 - n^ 2|

         y = 2*m*n

         z = m^2 + n^2

4-2、根據公式所示，可以設定下列條件：

    2-1：m的值小於(N/2)^0.5,n的值小於 (N^0.5)。

    2-2：當m為奇數時，則n必為偶數或當m為偶數時，則n必為奇數。   

    2-3：畢氏三元數的通式解的整數解無法完全解出非互質的畢氏三元數，因此必須依靠已求得的互質的畢氏

             三元數來計算其他非互質的畢氏三元數，並直接計算非畢氏三元數的整數數量。             

Run time of UVa online web : 0.304 ~ 0.312 sec

Download :   UVA106_FermatVSPythagoras.tar.gz

Result：