A-质数筛

按照题意，首先把数全部存在数组中，再挨着挨着判断是否是质数，若是质数则输出即可。

需要注意的是，判断质数时循环内应该采用类似i*i<=n的判断方法，而不需要枚举到n，这样可以节约很多时间。

暴力的素数判断可以通过此题，但建议采用在2022年6月双周赛2线性筛素数中学过的的方法，若没有掌握，可以参考此链接学习：https://www.luogu.com.cn/blog/cicos/notprime

如果没有掌握线性筛素数，至少要谨记：判断n是否是质数时，循环不需要枚举到n。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
bool isprime(int x){//判断是否素数
if(x<=1) return false;//如果小于2，一定不是素数
 for(int i=2;i*i<=x;i++){//如果有一个大于sqrt(n)的数可以被n整除，那么必有一个数n/i也可以被n整除且小于i
  if(x%i==0) return false;//如果可以整除，那么不是素数
 }
 return true;//是素数
}
int main(){
 int n,a;
 cin>>n;
 for(int i=1;i<=n;i++){
   cin>>a;
   if(isprime(a)){
     cout<<a<<" ";//是素数，就输出
   }
 }
 return 0;
}

B-彩票摇奖

一道简单的模拟题。我们可以用一个数组a来存储中奖号码的情况，即a[i]存储在中奖号码中i出现的次数。

然后，我们枚举买的彩票的号码。初始化某张彩票得了“七等奖”（即没有奖），让x=7。如果一个号码在a数组中值不为0，则表明中奖的等级提高，让x--。枚举完所有号码以后x的值即为最后得奖的层次，用b数组存储得各种奖的彩票张数，让b[x]++即可。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,sum;
int a[50],b[8];
int main()
{
scanf("%d",&n);
 for(int i=1;i<=7;i++)
 {
  int t;
  scanf("%d",&t);
  a[t]++;
 }
 for(int i=1;i<=n;i++)
 {
  int t,x=7;
  for(int j=1;j<=7;j++)
  {
    scanf("%d",&t);
    if(a[t]) x--;
  }
  b[x]++;
 }
 for(int i=0;i<=6;i++) printf("%d ",b[i]);
 return 0;
}

C-转圈游戏

此题的推理比较简单，x号每次走m步，由于是个环形，我们只需要每走一次对n取模即可得到相应位置。现在一共走了10^k次，所以最终答案很显然为 (x+m*10^k)\%n .

现在的问题在于如何计算10^k。由于k较大，直接循环k次很可能超时，我们需要用到快速幂的方法，同学们可以参考本链接学习，并可以在学习后尝试解决3730题：https://blog.csdn.net/qq_19782019/article/details/85621386

根据模运算的分配律，在计算10^k的过程中对n取模不影响我们最终的结果，所以我们只需要用快速幂算法求出10^k，再代入公式 (x+m*10^k)\%n 计算即可。

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,x;
long long pow(long long a,long long b,long long mod)
{
long long ans=1;
for(;b;b>>=1)
 {
   if(b&1) ans=ans*a%mod;
   a=a*a%mod;
 }
 return ans;
}
int main()
{
 scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
 printf("%lld",(x+pow(10,k,n)*m%n)%n);
 return 0;
}

D-野餐

大部分同学不会做这道题，是因为对图的相关知识不熟悉，建议复习图的相关内容进行巩固。

这道题其实很简单，我们从k个奶牛为起点分别dfs（或dfs），用ans[i]表示第i个牧场被遍历过多少次，最后只有ans[i]==k的牧场满足条件。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int k,n,m,val;
const int N = 10001;
struct edge
{
int next,to;
} e[N*2];
int head[N*2],tot,c[N],vis[N],s[N];
void add(int x,int y)
{
e[++tot].next=head[x];
head[x]=tot;
e[tot].to=y;
}
void bfs(int x)
{
queue<int>q;
q.push(x);
vis[x]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
vis[v]=1;
s[v]++;//每遍历到该点计数器加一
q.push(v);
}
}
}
}
int main()
{
scanf("%d%d%d",&k,&n,&m);
for(int i=1; i<=k; i++)
{
scanf("%d",&c[i]); //一开始先计数
s[c[i]]++;
}
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1; i<=k; i++)
{
memset(vis,0,sizeof(vis));//清空
bfs(c[i]);
}
int ans=0;
for(int i=1; i<=n; i++)
if(s[i]==k)ans++;//统计答案
printf("%d",ans);
}