蓝桥杯每日一题（筛质数、最大公约数）

3792 质数问题

用的埃氏筛法，st数组保存是否被筛掉，遍历到的st为0的节点就是质数，将其保存。

然后遍历所有相邻的节点得到判断是否存在条件中的质数。

#include<bits/stdc++.h>
using namespace std;
//3792 质数问题
const int N=1010;
vector<int>a;//保存所有质数
int st[N];
int main()
{

    int n,k,t;
    cin>>t;
    while(t--)
    {
        memset(st,0,sizeof(st));
        a.clear();
        cin>>n>>k;
        for(int i=2; i<=n; i++)
        {
            if(!st[i])
            {
                a.push_back(i);//保存质数
                for(int j=i+i; j<=n; j+=i)st[j]=1;

            }
        }
        int cnt=0;
        for(int i=0; i<a.size(); i++)
        {
            if(find(a.begin(),a.end(),a[i]+a[i+1]+1)!=a.end())
            {
                cnt++;
            }
        }
        //cout<<cnt<<"有"<<endl;
        if(cnt>=k)cout<<"YES"<<endl;
        else
        {
            cout<<"NO"<<endl;
        }
    }



}

 868. 筛质数(线性筛质数)

线性筛法

#include<bits/stdc++.h>
using namespace std;
//868 筛质数
const int N=1e6+10;
int prime[N];//记录所有的质数
int st[N];//是否被筛掉
int idx=0;
int n;
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])prime[idx++]=i;
        for(int j=0;j<idx;j++)
        {
            st[prime[j]*i]=1;//被筛掉了
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }
    cout<<idx<<endl;
}

4309 消灭老鼠

也就是消除所有的点需要几个不同的斜率。

记录每个斜率的分子分母的最大公约数，除以这个数之后每个斜率的分子分母就是唯一的。之后再出现这个点在这个斜率上，每次出现新的斜率就加加。

0和10的最大公约数是10。

解决了分母是0的情况。

#include<bits/stdc++.h>
using namespace std;
//4309 消灭老鼠
typedef pair<int,int>PII;
map<PII,int>mp;//保存某个斜率是否被保存过
//求最大公约数
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int n,x0,y0;
    cin>>n>>x0>>y0;
    int cnt=0;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        int x=(a-x0);
        int y=(b-y0);
        int maxx=gcd(x,y);
        x/=maxx;
        y/=maxx;
        PII t={x,y};
        if(mp[t]!=5)
        {
            mp[t]=5;
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

872. 最大公约数

模板题

#include<bits/stdc++.h>
using namespace std;
//872 最大公约数
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
   int n;
   cin>>n;
   while(n--)
   {
       int a,b;
       cin>>a>>b;
       cout<<gcd(a,b)<<endl;
   }
}

200 Hankson的趣味题

Segmentation Fault

是线性筛、分解质因数、欧几里得的结合。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int N=45000,M=50;
vector<PII>a;//质因子和次数
int st[N];
int idx=0;//约数下标
int idx2=0;//质数下标
int yue[N];//保存所有约数
int cntz=0;//有几个质因子
int prime[N];//所有素数
//最大公约数
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
//求所有的质数
void getprim(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            prime[idx2++]=i;
        }
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }

    }
}
//分解质因数
void fenjie(int n)
{
   //遇到一个数就将其榨干
   for(int i=0;prime[i]<=n/prime[i];i++)
   {
       int cnt=0;
       if(n%prime[i]==0)
       {
           while(n%prime[i]==0)
           {
               cnt++;
               n/=prime[i];
           }
       }
       a.push_back({prime[i],cnt});
       cntz++;
   }
   if(n>1)a.push_back({n,1}),cntz++;;

}


void dfs(int n,int m)
{
    if(n==cntz)
    {
        yue[idx++]=m;
        return;
    }
    else
    {
        //遍历某个质数的所有可能性
        int numofit=a[n].second;
        int num=a[n].first;
        for(int i=0;i<=numofit;i++)
        {

            dfs(n+1,m);
            m*=num;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a0,a1,b0,b1;
     //要找的x一定是b1的因数。//找到所有b1的因数
     //然后满足题目要求的条件
        cin>>a0>>a1>>b0>>b1;
        idx=0;//约数下标
        idx2=0;
        memset(yue,0,sizeof(yue));
        memset(prime,0,sizeof(prime));
        memset(st,0,sizeof(st));
        a.clear();
        cntz=0;//有几个质因子
        getprim(b1);
//        for(int i=0;i<idx2;i++)
//        {
//            cout<<prime[i]<<" ";
//        }
//     cout<<"以上为素数"<<endl;
       if(idx2)fenjie(b1);
//        for(int i=0;i<cntz;i++)
//        {
//            cout<<a[i].first<<" "<<a[i].second<<endl;
//        }
   // cout<<"以上为分解质因数"<<endl;

        dfs(0,1);
//         for(int i=0;i<idx;i++)
//        {
//            cout<<yue[i]<<" ";
//        }
//    cout<<"以上为因数"<<endl;
        int ans=0;
        for(int i=0;i<idx;i++)
        {
            int x=yue[i];
            if(gcd(x,a0)==a1&&(LL)(x*b0)/gcd(x,b0)==b1)
            {
                ans++;
                //cout<<x<<endl;
            }
        }
        cout<<ans<<endl;
    }


}