专栏文章

国庆day4数学考试--下午

CCrash_Man_CHN
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mino19kw
此快照首次捕获于
2025/12/02 05:33
3 个月前
此快照最后确认于
2025/12/02 05:33
3 个月前
查看原文

T3

题目思路

数列A是升序的，有两种情况A是个新的数字
1.当枚举的数是质数时，A自然是新的（第一次出现） 2.当枚举的数不是质数时，那么这个数质因数分解后其中一个指数肯定要大于a[i-1]的对应质数幂指数，所以这个枚举的数肯定是单个质数的幂，用素数幂即可解决
CPP
素数幂：
void prime_mi()
{
	vis[1]=1;
	for(int i=2;i<=1e7;i++)
	{
		if(!vis[i])prime.push_back(i);
		for(int j=0;j<prime.size()&&i*<=1e7;j++)vis[i*j]=1;
	}
	return ;
}

正解代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
bool vis[N],vis1[N];
vector<int> prime;
void e_prime()
{
	vis[1]=1;
	for(int i=2;i<=1e7;i++)
	{
		if(!vis[i])prime.push_back(i);
		for(int j=0;j<prime.size()&&i*<=1e7;j++)vis[i*j]=1;
	}
	return ;
}
signed main()
{
	int l,r;
	cin>>l>>r;
	l++;
	e_prime();
	int res=1;
	for(auto x:prime)
	{
		for(int j=x;j<=r;j++)
		{
			if(j>l)res++;
		}
		for(int j=(l+x-1)/x*x;j<=r;j+=x)vis1[j-l]=1;
	}
	for(int i=l+1;i<=r;i++)
	{
		if(vis1[i-l]==0)res++;
	}
	cout<<res;
	return 0;
}

T4

题目思路

先求出整个序列的LCM,如果LCM不在序列中，直接选整个序列，答案就是n

推理

LCM在序列中,LCM==max(a[i]) 所以序列中的所有数字都是LCM的约数 从而得知子序列的LCM必然也是LCM的约数

题目写法转化

枚举LCM的所有约数，看这个约数能够容纳下的序列数字的数量，答案直接去max

正解代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int a[N],n,maxn;
map<int,bool> vis;
vector<int> q;
int gcd(int a,int b)
{
	if(a%b==0)return b;
	return gcd(b,a%b);
}
int lcm(int a,int b)
{
	if(a==0)return 0;
	if(b==0)return 0;
	int g=gcd(a,b);
	return a/g*b;
}
void calc(int x)
{
	for(int i=1;i<=x/i;i++)
	{
		if(x%i==0)
		{
			q.push_back(i);
			if(x/i!=i)q.push_back(x/i);
		}
	}
}
int check(int x)
{
	int LCM=1,cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(x%a[i]==0)
		{
			LCM=lcm(LCM,a[i]);
			cnt++;
		}
	}
	if(LCM==x)return cnt;
	return 0;
}
void solve()
{
	vis.clear();
	q.clear();
	cin>>n;
	maxn=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxn=max(a[i],maxn);
		vis[a[i]]=1;
	}
	int LCM=1;
	for(int i=1;i<=n;i++)
	{
		LCM=lcm(LCM,a[i]) ;
		if(LCM>maxn)
		{
			cout<<n<<"\n";
			return ;
		}
	} 
	calc(LCM);
	int res=0;
	for(auto i:q)
	{
		if(vis[i])continue;
		res=max(res,check(i));
	}
	cout<<res<<"\n";
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--)solve();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...