20111028

ACM 10110 Light, more light

TL TL TL TL zzzz。
機車啊,害我想弄一個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;
}

沒有留言: