2011-10-16 09:36:05Morris
a247. Fermat vs. Pythagoras
a247. Fermat vs. Pythagoras
作法 : math + 建表
/**********************************************************************************/
/* Problem: a247 "Fermat vs. Pythagoras" from ACM 106 */
/* Language: C (1313 Bytes) */
/* Result: AC(101ms, 12MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-16 08:53:28 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxN 1000000
#define oo 2147483647
int gcd(int x, int y) {
int tmp;
while(x%y) {
tmp = x, x = y, y = tmp%y;
}
return y;
}
int mask1[MaxN+1], mask2[MaxN+1], Ans[MaxN+1];
int min(int x, int y) {
return x < y ? x : y;
}
int Build() {
int n, m, i, j, k, a, b, c;
for(i = 0; i <= MaxN; i++)
mask1[i] = oo;
memset(mask2, 0, sizeof(mask2));
memset(Ans, 0, sizeof(Ans));
for(i = 1; i < 1000; i++)
for(j = i+1; j < 1000; j += 2) {
if(gcd(i, j) > 1) continue;
a = j*j - i*i, b = 2*i*j, c = j*j + i*i;
if(c > MaxN) break;
mask2[c]++;
for(k = 1; k*c <= MaxN; k++) {
mask1[k*a] = min(k*c, mask1[k*a]);
mask1[k*b] = min(k*c, mask1[k*b]);
mask1[k*c] = min(k*c, mask1[k*c]);
}
}
for(i = 1; i <= MaxN; i++)
if(mask1[i] <= MaxN)
Ans[mask1[i]]++;
for(i = 1; i <= MaxN; i++) {
mask2[i] += mask2[i-1];
Ans[i] += Ans[i-1];
}
}
int main() {
int N;
Build();
while(scanf("%d", &N) == 1&& N) {
printf("%d %d\n", mask2[N], N-Ans[N]);
}
return 0;
}
/*利用此一性質，計算所有斜邊小於10000000的素勾股數，*/
/* abc為三邊 m > n 、 m 和 n 均是正整*/
/*a = m^2 -n^2, */
/*b = 2mn, */
/*c = m^2+n^2*/
內容 ：
著名的費馬大定理是指：當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）
輸出說明
：
輸出一列，含兩個整數，如題目所述，數字中間以一個空白字元分隔。
範例輸入
：
10 25 100 500 1000000
範例輸出 ：
1 4 4 9 16 27 80 107 159139 133926
提示
：
第一筆測資：範例測資
第二筆測資：1 <= N <= 1000000，N有10個
第三筆測資：1 <= N <= 1000000，N有1000個
第四筆測資：1 <= N <= 1000000，N有10000個
我想說全部建表比較快 可是竟然每次重新計算還比較快，討厭(?)
如果ACM還是ZJ上有AC 但是這邊WA的可以跟我反應 因為我丟UVa toolkit也跑不出output就TLE了
出處
：
ACM 106
(管理：no306100)
作法 : math + 建表
/**********************************************************************************/
/* Problem: a247 "Fermat vs. Pythagoras" from ACM 106 */
/* Language: C (1313 Bytes) */
/* Result: AC(101ms, 12MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-16 08:53:28 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxN 1000000
#define oo 2147483647
int gcd(int x, int y) {
int tmp;
while(x%y) {
tmp = x, x = y, y = tmp%y;
}
return y;
}
int mask1[MaxN+1], mask2[MaxN+1], Ans[MaxN+1];
int min(int x, int y) {
return x < y ? x : y;
}
int Build() {
int n, m, i, j, k, a, b, c;
for(i = 0; i <= MaxN; i++)
mask1[i] = oo;
memset(mask2, 0, sizeof(mask2));
memset(Ans, 0, sizeof(Ans));
for(i = 1; i < 1000; i++)
for(j = i+1; j < 1000; j += 2) {
if(gcd(i, j) > 1) continue;
a = j*j - i*i, b = 2*i*j, c = j*j + i*i;
if(c > MaxN) break;
mask2[c]++;
for(k = 1; k*c <= MaxN; k++) {
mask1[k*a] = min(k*c, mask1[k*a]);
mask1[k*b] = min(k*c, mask1[k*b]);
mask1[k*c] = min(k*c, mask1[k*c]);
}
}
for(i = 1; i <= MaxN; i++)
if(mask1[i] <= MaxN)
Ans[mask1[i]]++;
for(i = 1; i <= MaxN; i++) {
mask2[i] += mask2[i-1];
Ans[i] += Ans[i-1];
}
}
int main() {
int N;
Build();
while(scanf("%d", &N) == 1&& N) {
printf("%d %d\n", mask2[N], N-Ans[N]);
}
return 0;
}
/*利用此一性質，計算所有斜邊小於10000000的素勾股數，*/
/* abc為三邊 m > n 、 m 和 n 均是正整*/
/*a = m^2 -n^2, */
/*b = 2mn, */
/*c = m^2+n^2*/