2023-12-8
在vp div2的时候遇见了一道题
找不到看得懂的题解，但是大体应该是用的数论知识。正好趁这个机会补补数论的东西。
学习文章
算法学习笔记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;
}
这题我以前还写过，,,
#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
我是书背，写了半天是线性筛写错了,,
#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
#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;
}