1442开关灯（筛法、模拟）

Question

Description
Smart最近想出来一个新的游戏。现在有n个灯泡,它们的编号是1~n。Smart每次说两个数,找出它们的公共质因子,且每次把它们公共质因子的倍数编号灯泡按向灯泡的相反状态(原来开按为关,原来关按为开)。
Input
有多组数据，第一行一个整数t，表示测试数据的组数。
每组测试数据的第一行一个整数n，表示灯泡数，接下来有多行，每一行一对数，当输入“0 0”时，这组测试数据结束。
Output
每组测试数据输出一行，包含两个数，分别表示最终开、关灯泡的数目。
Sample Input
1
100
4 6
0 0
Sample Output
50 50
Hint
100%的数据：t≤10，2≤n≤10^6。
筛法、模拟

Answer 1

点个采纳，谢谢

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int p[1000030],ip[100020],num[1000010];
int k,sum;
int main()
{
    for(int i=2;i<=1000000;i++)
    {
        p[i]=0;
    }
    for(int i=2;i<1000;i++)
    {
        if(!p[i])
        {
            for(int j=2*i;j<=1000000;j+=i)
            {
                p[j]=1;
            }
        }
    }
    k=0;
    for(int i=2;i<=1000000;i++)
    {
        if(!p[i])
        {
            ip[k++]=i;
        }
    }
    int t,n;
    cin>>t;
    int a1,a2;
    int tm,min;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            num[i]=1;//开始时将所有的灯标为1 
        }
        while(cin>>a1>>a2)
        {
            if(a1==0&&a2==0)
            {
                break;
            }
            if(a1>a2)
            {
                min=a2;
            }
            else
            {
                min=a1;//求出最小值 
            }
            for(int i=0;i<k;i++)//在K个素数内寻找 
            {
                if(ip[i]<min)//以a1 a2的最小的那个为临界值 
                {
                    if(a1%ip[i]==0&&a2%ip[i]==0)//如果ip[i]的素数值能够被a1 a2同时整除 
                    {
                        tm=ip[i];//记录此值 
                        for(int j=tm;j<=n;j+=tm)//寻找此值的倍数，他的倍数也将被标记 
                        {
                            if(num[j])//如果此灯是1则改为零 
                            {
                                num[j]=0;
                            }
                            else//如果是零则改为1 
                            {
                                num[j]=1;
                            }
                        }
                    }
                }
            }
        }
        sum=0;
        for(int i=1;i<=n;i++)
        {
            sum=sum+num[i];//将所有为1的数加起来 
        }
        cout<<sum<<" "n-sum<<endl;
    }
    return 0;
 }