GHOJ 145 灯的开关状态

题目描述

        有N个灯放在一排，从1到N依次顺序编号。有N个人也从1到N依次编号。1号将灯全部关闭，2号将凡是2的倍数的灯打开；3号将凡是3的倍数的灯作相反处理(该灯如为打开的，则将它关闭；如关闭的，则将它打开)。以后的人都和3号一样，将凡是自己编号倍数的灯作相反处理。

        编程实现：第N个人操作后，按顺序输出灯的状态。(1表示灯打开，0表示灯关闭)

 

输入输出格式

输入格式

        一行，一个整数n，表示灯的个数。（1≤n≤5000000）

 

输出格式

        一行01序列，表示各盏灯的状态，中间无空格。输入输出样例

 

输入输出样例

输入样例

2

输出样例

01

 

题解

        设一个整数序列S=S1, S2,S3,...Sk使N=S1*Sk=S2*S(k-1)=...……

        显然，一般的k都是偶数，但当N为完全平方数是，因数可以相同，即k为奇数。此时把N看做灯的编号，当k为偶数时，最后结果为1，当k为奇数时，最后结果为0。

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int n, sn;

int main()
{
    scanf("%d", &n);
    sn = sqrt(n);
    for(register int i = 1; i <= sn; ++i)
    {
        putchar('0');
        for(register int j = i * i + 1; j < (i + 1) * (i + 1) && j <= n; ++j)
        {
            putchar('1');
        }
    }
    return 0;
}