2023-12-8

在vp div2的时候遇见了一道题

Problem - D - Codeforces

找不到看得懂的题解，但是大体应该是用的数论知识。正好趁这个机会补补数论的东西。

学习文章

算法学习笔记27：素数筛法【埃氏筛法、线性筛法】 - 知乎 (zhihu.com)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

constexpr int N = 3e5 + 10, md = 1e9 + 7;
const int M = (int)(1.5e7 + 2);
int a[N], cnt[M];
int prime[M / 10];
bool vis[M];
int n;

void pr(int tt){
    vis[1]=true;
    for(int i=2;i<=tt;i++){
        if(!vis[i]) prime[++prime[0]]=i;
        for(int j=1;i*prime[j]<tt;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

void solve(){
    cin>>n;
    int d=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d=__gcd(d,a[i]);
    }
    int cx=0;
    for(int i=1;i<=n;i++)
    {
        a[i]/=d;
        cx=max(cx,a[i]);
        cnt[a[i]]++;
    }
    pr(cx);

    int ans=0;
    for(int i=1;i<=prime[0];i++)
    {
        int ct=0;
        for(int j=prime[i];j<=cx;j+=prime[i])
            ct+=cnt[j];
        if(ct>0)ans=max(ans,ct);
    }
    cout<< (ans==0 ? -1 : n-ans) <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}

Problem - D - Codeforces

这题我以前还写过，,,

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int mod = 998244353;
const int N   = 1e5 + 10;
int a[N];
int f[N];
int n;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            f[i] = max(f[i],a[j]);
    sort(f+1,f+1+n);
    long long ans = 0;
    long long x   = 1;
    for(int i=1;i<=n;i++){
        ans = (ans + (x*f[i]%mod)%mod)%mod;
        x   =  x*2%mod;
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}

803F - Coprime Subsequences

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int mod = 1e9 + 7;
const int N   = 1e5 + 10;
long long a[N],ans[N],cnt[N];
long long pow1[N];
int n;

void solve(){
    cin>>n;
    pow1[0]=1;
    int cx=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        cnt[a[i]]++;
        pow1[i] = (pow1[i-1] << 1) % mod;
        cx = max(cx,a[i]);
    }
    for(int i=1;i<=cx;i++)
        for(int j=i*2;j<=cx;j+=i)
            cnt[i] += cnt[j];
    for(int i=cx;i>0;i--)
    {
        ans[i]=pow1[cnt[i]]-1;
        for(int j=2*i;j<=cx&&j<N;j+=i)
        {
            ans[i] -= ans[j];
            if(ans[i]<0) ans[i] += mod;  //因为前面取过模，所以这里要注意
        }
    }
    cout<<ans[1]<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}

C. Jzzhu and Apples

Problem - 449C - Codeforces

我是书背，写了半天是线性筛写错了,,

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n;
int prime[N];
bool vis[N];
void pr(){
    vis[1]=true;
    for(int i=2;i<N;i++){
        if(!vis[i]) prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]*i<N;j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

void solve(){
    cin>>n;
    pr();
    vector<pair<int,int>> ans;
    memset(vis,false,sizeof vis);
    for(int i=prime[0];i>0;i--){
        vector<int> a;
        for(int j=prime[i];j<=n;j+=prime[i])
            if(!vis[j]) a.push_back(j);
        int len=a.size();
        if(len<=1) continue;
        if(len&1){
            ans.push_back({a[0],a[len-1]});
            vis[a[0]]=vis[a[len-1]]=true;
            for(int j=2;j<len-1;j+=2){
                ans.push_back({a[j],a[j+1]});
                vis[a[j]]=vis[a[j+1]]=true;
            }
        }else{
            for(int j=0;j<len;j+=2){
                ans.push_back({a[j],a[j+1]});
                vis[a[j]]=vis[a[j+1]]=true;
            }
        }
    }
    cout<<ans.size()<<endl;
    for(auto [x,y]:ans) cout<<x<<" "<<y<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}

D. Counting Rhyme

Problem - D - Codeforces

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 10;
int a[N] , cnt[N];
int f[N]; //fi:gcd恰好为i的对数
bool vis[N];
int n;

void solve(){
    cin>>n;
    for(int i=0;i<=n;i++){
        vis[i]=false;
        f[i]=0;
        cnt[i]=0;
        a[i]=0;
    }
    int cx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
        cx = max(cx , a[i]);
    }
    for(int i=1;i<=cx;i++)
        for(int j=2*i;j<=cx;j+=i)
            cnt[i] += cnt[j];
    for(int i=cx;i>0;i--){
        f[i] = cnt[i]*(cnt[i]-1)/2;
        for(int j=2*i;j<=cx;j+=i)
            f[i] -= f[j];
    }
    for(int i=1;i<=cx;i++)
        for(int j=a[i];j<=cx;j+=a[i]) vis[j]=true;
    long long ans=0;
    for(int i=1;i<=cx;i++)
        if(!vis[i]) ans+=f[i];
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}