a247: 00106 - Fermat vs. Pythagoras
標籤 :
通過比率 : 49% (43 人 / 87 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2013-07-28 01:13

內容
著名的費馬大定理是指:當n>2時,xn+yn=zn 無整數解,這邊我們要處理的問題跟費馬大定理有點關係。

給你一個正整數 N,你的任務是算出兩個與方程式 x2+y2=z的解相關的數字。( 0 < x < y < z <= N )

第一個數字是互質的數對(triples) (x,y,z) 數目。互質是指 x、y、z 沒有大於 1 的公因數。第二個數字p是在 小於等於 N 的數字內不屬於任何數對 (x,y,z) 的正整數總數,這邊 x、y、z不需要互質。

例如,N=10,可找到一組 互質數對 (3,4,5)  及 一組不互質的數對 (6,8,10), 1、2、7、9 共 4 個數字沒用到。所以N=10要輸出1與4。
輸入說明
輸入含有多組測試資料,每組測試資料一列,有一個正整數 N (1 <= N <= 1000000)
輸出說明

輸出一列,含兩個整數,如題目所述,數字中間以一個空白字元分隔。

 

範例輸入
10
25
100
500
1000000
範例輸出
1 4
4 9
16 27
80 107
159139 133926
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
提示 :

第一筆測資:範例測資

第二筆測資:1 <= N <= 1000000,N有10個

第三筆測資:1 <= N <= 1000000,N有1000個

第四筆測資:1 <= N <= 1000000,N有10000個 

 10/16 13:05 新增:

第五筆測資:1 <= N <= 1000000,N有100000個

時限縮短為 2s Rejudge

 

我想說全部建表比較快 可是竟然每次重新計算還比較快,討厭(?)

如果ACM還是ZJ上有AC 但是這邊WA的可以跟我反應 因為我丟UVa toolkit也跑不出outputTLE 

 

標籤:
出處:
UVa106 [編輯:
no306100 (JamesQAQ)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」