機車啊,害我想弄一個array把1到65535的次方
放進去。
觀察法: 1 2 3 4 5 6 7 8 9 10 (燈泡) 1 y y y y y y y y y y 2 y n y n y n y n y n 3 y n n n y y y n n n 4 y n n y y y y y n n 5 y n n y n y y y n y 6 y n n y n n y y n y 7 y n n y n n n y n y 8 y n n y n n n n n y 9 y n n y n n n n y y 10 y n n y n n n n y n (次數)row是次數,
column是燈泡。
求第n次,第n個燈泡是亮還是不亮。
所以1到10的解分別是
1 2 3 4 5 6 7 8 9 10
y n n y n n n n y n
想法很簡單,
判斷第i個燈泡是否有因數。
沒因數 => 質數 => 不亮,
有因數 => 合數,
合數兩種情況,
(1)有單數個因素 => 亮
(2)有雙數個因素 => 不亮
以10為例,
1x10 = 2x5 = 5x2 = 10x1 = 10
1, 2, 5, 10所以不亮。
之後簡化,算到根號n就好,
(因為合數必然是兩個數相乘,
兩者之一必有一數大於等於根號n,另一數小於等於根號n)
所以5, 10都可以去掉,
1必然是因素,也去掉。
剩2,單個,但2表示2x5 = 5x2 = 10。
說是單個,要乘以2,實際上是雙數,
唯一一種例外情況,以16為例,
2, 4,兩個,2x8 = 8x2 = 16,
但4x4 = 4x4 = 16,只能算一個。
得到結論:若根號n為n的因素,只能算一個。
這種情況,就是亮(單數個因素)
再往下推,
所以不管因素有幾個,
如果根號n是因素,那必定是單數個因素,
根號n不是因素,必定是雙數個因數。
這樣就很簡單了,
只要判斷根號n是否為n的因素,
就知道第n個燈泡會不會亮。
但是慢慢算還是會TL的(我就是),
所以要嘛用一個超大的array事先算好1~65535的次方數,
要嘛就用math.h函式庫的sqrt()幫忙算根號n。
機車測資啊……
i用unsigned就好,long long會快一點。
/* ACM 10110 * mythnc * 2011/10/28 11:20:00 * run time: 0.032 */ #include <stdio.h> #include <math.h> #define YES 1 #define NO 0 int factor(double n); int main(void) { double n; while (scanf("%lf", &n)) { if (n == 0) return 0; if (n == 1 || factor(n) == YES) printf("yes\n"); else printf("no\n"); } } /* factor: calculate the square root of n is integer or not * if is return 1 else return 0 */ int factor(double n) { long long i; i = sqrt(n); if (i * i == n) return YES; else return NO; }
沒有留言:
張貼留言