补题*总结题21/8/25

C - Coprime 2

题意:
给出n个数,在[1,m]范围那找出与这n个数都互质的数。

思路1:

直接暴力,结果不出所料
时间复杂度O(n* m),直接超时
代码:

展开源码


int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a% b);
}
int main()
{
    int i,j;
    int n,m;
    cin>>n>>m;
    int a[100001];
    for(i=0; i<n; i++)="" cin="">>a[i];
    int data[100001];
    long long int o=0;
    long long  int sum;
    o=0;
    for(j=1; j<=m; j++)
    {
        if(gcd(j,a[0])==1)
        {
            data[o]=j;
            o++;
        }
    }
    sum=o;

    for(i=1; i< n ;  i++)
    {
        for(j=0; j < o; j++)
        {
            if( data[j]!=-1)
            {
                if( gcd(data[j],a[i])!=1 )
                {
                    data[j]=-1;
                    sum--;
                }
            }
        }
    }

    cout<< sum << endl;
    for(i=0 ; i< o;  i++)
    {
        if(data[i]!=-1)
            cout<< data[i]<< endl;
    }
    return 0;

}

思路2

做数组data[m],其中data[j]=0代表数j符合题意,data[j]=1代表不符合题意。
判断a[i]是否为质数,如果是质数则把1~m之间的a[i]的倍数赋值为1;
若不为质数,则把a[i]的质因数,在1~m之间的倍数赋值为1
代码:

**#include <bits/stdc++.h>
using namespace std;


int main()
{
    int i,j;
    int n,m;
    cin>>n>>m;
    int a[100001];
    for(i=0; i<n; i++)   cin>>a[i];
    int data[100001]= {0};
    int sum=m;
    int flag=0;
    int k;
    for(i=0; i<n; i++)
    {
        flag=0;//默认是质数
        if(a[i]==1){flag=1;}
        else
        if(a[i]==2||a[i]==3)
         {
             flag=0;
         }
        else
        {
            for(j=2; j*j<=a[i]; j++)
            {
                if(a[i]%j==0)
                {
                    flag=1;
                     for(k=1;j*k<=m;k++)
                     {
                         if(data[k*j]!=1)
                         {data[k*j]=1;
                         sum--;}
                     }
                    for(k=1;(a[i]/j)*k<=m;k++)
                     {
                         if(data[k*(a[i]/j)]!=1)
                         {data[k*(a[i]/j)]=1;

                         sum--;}
                     }
                }

            }
        }
        if(flag==0)
        {
            for(k=1;a[i]*k<=m;k++)
            {
                if(  data[ a[i]*k ]!=1)
                {data[ a[i]*k ]=1;
                sum--;
                }
            }
        }

    }



    cout<<sum<<endl;
    for(i=1; i<=m; i++)
    {
        if(data[i]==0)
            cout<<i<<endl;
    }
    return 0;

}
**

结果还是超时,但是比暴力快,继续优化。

思路3

思路2超时,应该是因为有公共质因数,重复给data[j]赋值导致,尝试在原函数上修改无果后,开启思路三

可以先把质因数找好标记上 ,然后,那么将不互质的数剔除。

代码:


上一篇:HDU-4292-Food(最大流,Dinic)


下一篇:【最短路径】回家