2011-06-10 20:05:35Morris
d903. 數學達人
http://zerojudge.tw/ShowProblem?problemid=d903
內容 ：
有一個人叫黃信元，是一位神秘的小小國中生
他的數學很好，每次都考第一名
有一次黃信元的數學老師在徵求數學達人
題目如下:
有一個數字a
然後畫出每一條邊有a個點
假設a=3
圖形就畫出像以下此圖
● ● ●
● ● ●
● ● ●
接著有一條橡皮筋
問可圍出幾個正方形?(正方形的四個角必須在點上)
像3*3的一看就知道答案是6(邊長1*1有4個 邊長2*2有1個 邊長√2*√2有1個)
所以輸出6
可是老師說只要算出a=100000時的答案就是數學達人
黃信元一看愣住了
幫幫他寫一個程式吧
輸入說明 ：
輸入只有一個正整數 a (0<a<=100000)
輸出說明 ：
輸出答案
範例輸入 ：
123
範例輸出 ：
016
提示 ：
如果AC了 寫寫看d910
*測資有改 2011/3/10
*由於JAVA不能在4MB內AC本題，故將空間限制放寬到8MB。
出處 ：
我們在數 l = 3 時，會得到很多左圖的黑色框框
然而，我們找到一個斜的正方形時，必然可以用4個三角形使其補成一個正方形，
因此在 l = 3，裡面又含有 2 個斜的正方形 (所有點都要在正立的正方形上)
類推 l = 4，裡面又有 3 個斜的正方形
最後得到
中間過程，忽略，如真有需要，請留言
/**********************************************************************************/
/* Problem: d903 "數學達人" from me */
/* Language: C */
/* Result: AC (6ms, 278KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-05 17:20:06 */
/**********************************************************************************/
#include<stdio.h>
long long reduce_fraction(long long *a, long long *b) {
long long x = *a, y = *b, t;
while(x%y) {
t = x, x = y, y = t%y;
}
*a /= y, *b /= y;
}
main() {
long long n;
while(scanf("%lld", &n) == 1) {
long long U1 = n*n, L = 12, U2 = n*n-1;
reduce_fraction(&U1, &L);
reduce_fraction(&U2, &L);
unsigned long long Ans = U1 * U2;
printf("%llu\n", Ans);
}
return 0;
}
上一篇：d832. 遊樂場
下一篇：d910. 數學達人2