国庆day4数学考试--下午

Crash_Man_CHN · 2025-10-07 16:52:18 · 个人记录

T3

题目思路

数列A是升序的，有两种情况A是个新的数字

1.当枚举的数是质数时，A自然是新的（第一次出现） 2.当枚举的数不是质数时，那么这个数质因数分解后其中一个指数肯定要大于a[i-1]的对应质数幂指数，所以这个枚举的数肯定是单个质数的幂，用素数幂即可解决

素数幂：
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 ;
}

正解代码

#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

正解代码

#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;
}