oj问题062开关电灯

游啊游

描述
N盏灯排成一排，从1到N依次编号。有N个人也同样编号。
第一个人将灯全部熄灭；
第2个人将对应2和2的倍数的灯打开；
第3个人将对应着3和3的倍数的灯做反向操作（如果原来是开，则关掉它，否则就打开它）；
以后的人和3做同样的操作，即第i个人将对应着i和i的倍数的灯做反向操作。
输入
灯的总数N, 1<=N<=1000
输出
在第N个人操作后，顺序输出还亮着灯的编号。
样例输入
8
样例输出
2 3 5 6 7 8

为什么我写的代码一直wa，哪里出错了，求指教

#include<iostream>
#define N 1000
using namespace std;
int main()
{
        int i,j,n;
        int a[N]={0};
        cin>>n;
        for(i=2;i<=n;i++)
                for(j=i;j<=n;j++)
                        if(j%i==0)
                                a[j]=!a[j];
        for(i=1;i<=n;i++)
                if(a[i])
                        cout<<i<<" ";
        cout<<endl;
        return 0;
}

迷雾少年

#include<iostream>
#define N 1000
using namespace std;
int main()
{
        int i,j,n;
        int a[N]={0};
        cin>>n;

        for(i=2;i<=n;i++)
                for(j=i;j<=n;j++)
                        if(j%i==0)
                                a[j-1]=!a[j-1];


        for(i=0;i<n;i++)
                if(a[i])
                        cout<<i+1<<" ";
        cout<<endl;
        return 0;
}

游啊游

迷雾少年 发表于 2016-8-20 18:33

明白了......
oj的测试数据应该是1000
我的有效空间是999
将N define为1001果然accepted
我的算法时间复杂度已到n方级
有没有更省时间的做法？

迷雾少年

游啊游 发表于 2016-8-20 19:26
明白了......
oj的测试数据应该是1000
我的有效空间是999

#include<iostream>
#define N 1000
using namespace std;
int main()
{
        int i,j,n;
        int a[N]={0};
        cin>>n;

        for(i=2;i<=n;i++)
                for(j=i;j<=n;j+=i)
                        if(j%i==0)
                                a[j-1]=!a[j-1];


        for(i=0;i<n;i++)
                if(a[i])
                        cout<<i+1<<" ";
        cout<<endl;
        return 0;
}

迷雾少年

游啊游 发表于 2016-8-20 19:26
明白了......
oj的测试数据应该是1000
我的有效空间是999

格式最好改下。。。

游啊游

迷雾少年 发表于 2016-8-20 22:47
格式最好改下。。。

什么格式？

迷雾少年

游啊游 发表于 2016-8-21 11:11
什么格式？

加点括号。。。

游啊游

迷雾少年 发表于 2016-8-21 11:15
加点括号。。。

紫瞰

学习一下