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，哪里出错了，求指教

1. #include<iostream>
   
2. #define N 1000
   
3. using namespace std;
   
4. int main()
   
5. {
   
6.         int i,j,n;
   
7.         int a[N]={0};
   
8.         cin>>n;
   
9.         for(i=2;i<=n;i++)
   
10.                 for(j=i;j<=n;j++)
    
11.                         if(j%i==0)
    
12.                                 a[j]=!a[j];
    
13.         for(i=1;i<=n;i++)
    
14.                 if(a[i])
    
15.                         cout<<i<<" ";
    
16.         cout<<endl;
    
17.         return 0;
    
18. }

复制代码

迷雾少年

1. #include<iostream>
   
2. #define N 1000
   
3. using namespace std;
   
4. int main()
   
5. {
   
6.         int i,j,n;
   
7.         int a[N]={0};
   
8.         cin>>n;
   
9. 
   
10.         for(i=2;i<=n;i++)
    
11.                 for(j=i;j<=n;j++)
    
12.                         if(j%i==0)
    
13.                                 a[j-1]=!a[j-1];
    
14. 
    
15. 
    
16.         for(i=0;i<n;i++)
    
17.                 if(a[i])
    
18.                         cout<<i+1<<" ";
    
19.         cout<<endl;
    
20.         return 0;
    
21. }

复制代码

游啊游

迷雾少年 发表于 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
加点括号。。。

紫瞰

学习一下