C. Hossam and Trainees

地址跳转

筛出1-N中的质数，打上标记，存入prime数组
欧拉筛，时间复杂度：$O(n)$
每个数只会被它的最小质因子筛一次

void ola(){
	for(int i=1;i<=N;i++){
		if(!vis[i]) prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}

把每一个数分解质因数，
如果之前有过相同的质因数，就返回true
否则把该质因数标记

bool check(int x){
	for(int j=1;j<=cnt&&prime[j]<=x;j++){
		if(x%prime[j]==0){
			if(mp[prime[j]]) return 1;
			mp[prime[j]]=1;
			while(x%prime[j]==0) x/=prime[j];
		}
	}
	if(x>1){
		if(mp[x]) return 1;
		mp[x]=1;
	}
	return 0;
}

依次检查每个数

mp.clear();
int flag=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
	if(check(a[i])) flag=1;
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;

完整代码：

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

using namespace std;

const int N=32000;

int prime[N],vis[N],cnt,sum[N];
map<int,int> mp; 

void ola(){
    for(int i=2;i<=N+5;i++){
        if(!vis[i]){
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

bool check(int x){
    for(int j=1;j<=cnt&&x>=prime[j];j++){
        if(x%prime[j]==0){
            if(mp[prime[j]]){
                return 1;
            }
            mp[prime[j]]=1;
            while(x%prime[j]==0){
                x/=prime[j];
            }
        }  
    }
    if(x>1){
        if(mp[x]) return 1;
        mp[x]=1;
    }
    return 0;
}

void solve(){
    int n;
    cin>>n;
    int a[100005];
    mp.clear();
    int flag=0;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++){
        if(check(a[i])) flag=1;
    }
    if(!flag) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    ola();
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

---

D. Same Count One

地址跳转

统计每一行1的个数和总1的个数

for(int i=1;i<=n;i++) 	G[i].clear();
for(int i=1;i<=n;i++){
	G[i].push_back(0);
	cnt[i]=0;
	for(int j=1;j<=m;j++){
		G[i].push_back(0);
		cin>>G[i][j];
		cnt0+=G[i][j];
		cnt[i]+=G[i][j];
	}
	if(cnt%n){
		cout<<-1<<endl;
		return ;
	}
}

先枚举每一列，再找到哪一行多1，哪一行少1，进行交换
交换后记得更改cnt[i]的值

for(int j=1;j<=m;j++){
	a.clear();b.clear();
	for(int i=1;i<=n;i++){
		if(cnt[i]<cnt0&&!G[i][j]) a.push_back(i);
		if(cnt[i]>cnt0&&G[i][j]) b.push_back(i);
	}
	for(int i=0;i<min(a.size(),b.size());i++){
		ans++;
		ansx[ans]=a[i],ansy[ans]=b[i],ansz[ans]=j;
		cnt[a[i]]++,cnt[b[i]]--;
	}
}

把答案提前存进ansx ansy ansz数组里，
最后输出

完整代码：

cout<<ans<<endl;
for(int i=1;i<=ans;i++)	
	cout<<ansx[i]<<' '<<ansy[i]<<' '<<ansz[i]<<endl;

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

using namespace std;

const int N=100010,M=1000010;
int n,m;
int cnt[N],cnt0;
vector<int> G[N],a,b;
int ans,ansx[M],ansy[M],ansz[M];

void solve(){
    cnt0=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) G[i].clear();
    for(int i=1;i<=n;i++){
        G[i].push_back(0);
        cnt[i]=0;
        for(int j=1;j<=m;j++){
            G[i].push_back(0);
            cin>>G[i][j];
            cnt0+=G[i][j];
            cnt[i]+=G[i][j];
        }
    } 
    if(cnt0%n){
        cout<<-1<<endl;
        return ;
    }
    cnt0/=n;
    ans=0;
    for(int j=1;j<=m;j++){
        a.clear();b.clear();
        for(int i=1;i<=n;i++){
            if(cnt[i]<cnt0&&!G[i][j]) a.push_back(i);
            if(cnt[i]>cnt0&&G[i][j]) b.push_back(i);
        }
        for(int i=0;i<min(a.size(),b.size());i++){
            ans++;
            ansx[ans]=a[i],ansy[ans]=b[i],ansz[ans]=j;
            cnt[a[i]]++,cnt[b[i]]--;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)
        cout<<ansx[i]<<' '<<ansy[i]<<' '<<ansz[i]<<endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

---

C. Interesting Sequence

地址跳转

lowbit(x)的意义是x的二进制的最低位的1代表的十进制数

int lowbit(int x){
	return x&-x;
}

判断是否有某一位，a为0且b为1

int a,b;
cin>>a>>b;
int na=a,nb=b;
vector<int> A,B;
while(a){
	A.push_back(a&1);
	a>>=1;
}
while(b){
	B.push_back(b&1);
	b>>=1;
}
while(A.size()<B.size()) A.push_back(0);
while(A.size()>B.size()) B.push_back(0);

for(int i=0;i<A.size();i++){
	if(!A[i]&&B[i]){
		cout<<-1<<endl;
		return ;
	}
}

让a不断地加lowbit(a)，因为只有不断地加lowbit(a)才有可能有效果
其余数可以证明都是无效数
&是单调递减的
让na不断地&a，若na<nb，则为不可能
最终要么等于要么小于

a=na;
while(na!=nb){
	a+=lowbit(a);
	na=na&a;
	if(na<nb){
		cout<<-1<<endl;
		return ;
	}
}
cout<<a<<endl;

完整代码：

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

using namespace std;

int lowbit(int x){
    return x&(-x);
}

void solve(){
    int a,b;
    cin>>a>>b;
    int na=a,nb=b;
    vector<int> A,B;
    while(a){
        A.push_back(a&1);
        a>>=1;
    }
    while(b){
        B.push_back(b&1);
        b>>=1;
    }

    while(A.size()<B.size()) A.push_back(0);
    while(A.size()>B.size()) B.push_back(0);

    for(int i=0;i<A.size();i++){
        if(A[i]!=B[i]&&!A[i]){
            cout<<-1<<endl;
            return ;
        }
    }

    a=na;
    while(na!=nb){
        a+=lowbit(a);
        na=na&a;
        if(na<nb){
            cout<<-1<<endl;
            return ;
        }
    }
    cout<<a<<endl;
    return ;
}

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