2011-06-01 22:21:35Morris
d416. 投影最大值
http://zerojudge.tw/ShowProblem?problemid=d416
內容 ：
給定長方體三邊長M、N、L
1<=M、N、L<=150
空間中有一平面a使得長方體投影在平面a上的面積有最大值
可以想像這個投影後的圖形應當是個六邊形(不一定正六邊形)會最大
所以請輸出這面積最大值
輸入說明 ：
每行輸入三正整數M、N、L
1<=M、N、L<=150
輸出說明 ：
請輸出此長方體在空間對所有平面的投影中面積的最大值
並且測資保證答案可以表示為a_/b的形式
其中a、b為正整數
特別的當a=1只要輸出_/b
b=1只要輸出a
範例輸入 ：
6 6 83 12 150 0 0
範例輸出 ：
12_/41189
提示 ：
背景知識： math
出處 ：
/**********************************************************************************/
/* Problem: d416 "投影最大值" from david */
/* Language: C */
/* Result: AC (96ms, 408KB) on ZeroJudge */
/* Author: morris1028 at 2011-05-31 23:19:24 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
int gcd(int x, int y) {
int t;
while(x%y) {
t = x, x = y, y = t%y;
}
return y;
}
long long P[5200], pt = 0;
void P_Sieve() {
char mark[100000] = {};
int a, b;
P[pt++] = 2;
for(a = 3; a <= 50000; a += 2)
if(mark[a] == 0) {
P[pt++] = a;
for(b = 3; a*b <= 50000; b += 2)
mark[a*b] = 1;
}
}
main() {
P_Sieve();
int M, N, L, t, tx, a;
while(scanf("%d %d %d", &M, &N, &L) == 3) {
if(M + N + L == 0) break;
tx = gcd(M, gcd(N, L)), M/=tx, N/=tx, L/=tx;
if(M > L) t = M, M = L, L = t;
if(N > L) t = N, N = L, L = t;
if(M > N) t = N, N = M, M = t;
long long V = N*L*N*L + M*M*(N*N+L*L);
long long t1 = 1, t2 = V;
for(a = 0; a < pt && t2 >= P[a]*P[a]; a++)
while(t2%(P[a]*P[a]) == 0)
t1 *= P[a], t2 /= P[a]*P[a];
t1 *= tx * tx;
if(t1 == 1 && t2 != 1)
printf("_/%lld\n", t2);
else if(t2 != 1)
printf("%lld_/%lld\n", t1, t2);
else
printf("%lld\n", t1);
}
return 0;
}
上一篇：d825. 隔熱紙