a247.
00106 - Fermat vs. Pythagoras
內容
著名的費馬大定理是指：當n>2時，xn+yn=zn 無整數解，這邊我們要處理的問題跟費馬大定理有點關係。
給你一個正整數 N，你的任務是算出兩個與方程式 x2+y2=z2 的解相關的數字。( 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，你的任務是算出兩個與方程式 x2+y2=z2 的解相關的數字。( 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）
輸出說明
輸出一列，含兩個整數，如題目所述，數字中間以一個空白字元分隔。
範例輸入
#1
10 25 100 500 1000000
範例輸出
#1
1 4 4 9 16 27 80 107 159139 133926
測資資訊：
記憶體限制：
512
MB
提示 ：
第一筆測資：範例測資
第二筆測資：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也跑不出output就TLE了
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 29449 |
|
a247 | 688 | 2022-03-02 23:04 |