问题描述

有n只灯泡排成一条线，编号分别为1,2,...,n。初始状态灯泡都是不亮的。在这些灯泡上执行一系列的开关灯操作。这些操作的编号为1,2,3,.....，第i次操作把编号为i的倍数的灯泡的开关状态变换一下（亮的变成不亮，不亮的变成亮）。

输入

每个测试数据值为包含一个整数n ( 0< n<= 10^5)单独一行构成，由多个测试数据，输入有EOF结束。

输出

对每种情况，输出执行了无穷多次开光灯操作后第n只灯泡的状态。0表示灯不亮，1表示等亮。每个测试数据的输出单独一行。

输入样例

1
5

输出样例

1
0

LZ学习精神让我钦佩，不过LZ思考不太深，这样对学习不大好，我提供下思路，不提供代码，这题我以前做过，就按它的意思暴力算（精简点，我印象中不会超时）应该不会超时···不知道LZ试过没，还有一种就是观察规律，换个思路这题就是求一个数的约数的个数。
    因为改变灯的状态是要i的倍数才行。而当i>n时，i是不会改变n的状态了，就是说，i>n,后就不会理了，前面的话，也就只有i = 1;和i为n的约束时，才能改变灯的状态····
    LZ好好思考下··

学习了，谢谢哦

scanf("%d",&n);
for(i=1;i<=n;i++)
{k=n/i;
for(j=1;j<k;j++)
{if(a[i*j]==0)a[i*j]=1;
else a[i*j]=0;}
}

有点不太明白

4L···直接模拟····

#include<stdio.h>
int main()
{
    int n,a[100000],i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            k=n/i;
            for(j=1;j<k;j++)
            {
                if(a[i*j]==0)
                    a[i*j]=1;
                else
                    a[i*j]=0;
            }
        }
        printf("%d\n",a[i*j]);
    }
    return 0;
}
输出答案全是0,怎么会事?

#include<stdio.h>
int main()
{
    int n,i,j,k,a;
    while(scanf("%d",&n)!=EOF && 0<=n && n<=100000)
    {
        a=0;
        for(i=1;i<=n;i++)
        {
            if(n%i==0)
            {
                if(a==0)
                    a=1;
                else
                    a=0;
            }
            if(i==n)
                printf("%d\n",a);
        }
    }
    return 0;
}
我重新改成这样怎么样?

#include<stdio.h>
int main()
{
    int n,a[100000] = {0},i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            k=n/i;
            for(j=1;j<=k;j++)
            {
                if(a[i*j]==0)
                    a[i*j]=1;
                else
                    a[i*j]=0;
            }
        }
        printf("%d\n",a[n]);
    }
    return 0;
}

8s 应该可以AC吧，不过建议LZ养成好的习惯，写的代码尽量复杂度小点，这道题可以小于o(n^1/2)的···