牛客暑假多校2020第四场H题, 思维题
程序员文章站
2022-04-03 08:54:10
...
https://ac.nowcoder.com/acm/contest/5669/H
H-Harder Gcd Problem
题意:在1~n中选出2*m个数,排成两列数组长度p,q分别为m,且gcd(p,q)>1,问m最大为多少,且打印出你的两列数组
思路:先用素数筛法,从小到大把2~n的数存放进一个二维数组,其中每一列的开头为素数,之后的以为为这个素数的倍数,而且整个二维数组没有重复的数,这里要进行一个记录。然后从大到小对这些筛选出来的数进行挑出,如果长度为偶数,那么直接筛出,如果长度为奇数,那么最小那个在素数2中选出,即选这个素数的两倍,最后对素数为2的倍数的数组进行挑出,即可。
代码如下:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define per(i, a, n) for(int i = n-1; i >= a; i--)
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define INF 1ll<<60
#define fopen freopen("file.in","r",stdin);freopen("file.out","w",stdout);
#define fclose fclose(stdin);fclose(stdout);
const int maxn = 2e5+10;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
bool isp[maxn];
int p[maxn], len=0;
void init() {
isp[0] = isp[1] = true;
for (int i = 2; i < maxn; i++) {
if(!isp[i]) p[++len] = i;
for (int j = 1; j <= len && p[j]*i < maxn; j++) {
isp[i*p[j]] = true;
if (i%p[j] == 0) break;
}
}
}
vector<int> v[maxn];
bool vis[maxn], vis1[maxn];
void cf(){
int t;
t = read();
while(t--){
int n = read();
int pos = 0;
vector<pii> m;
memset(v,0,sizeof(v));
for(int i = 0; i <= n; i++) vis[i]=vis1[i]=0;
for(int i = 1; i <= n; i++){
if(p[i]>n) break;
pos = i;
for(int j = 1; j < n; j++){
int x = j*p[i];
if(x<=n){
if(!vis[x]) v[i].push_back(x);
vis[x] = 1;
}else break;
}
}
for(int i = pos; i >= 2; i--){
int cnt = v[i].size();
if(cnt%2==0){
for(int j = 0; j < cnt; j+=2){
m.push_back(pii{v[i][j], v[i][j+1]});
}
}else {
for(int j = 1; j < cnt; j+=2){
m.push_back(pii{v[i][j], v[i][j+1]});
}
if(v[i][0]*2<=n){
m.push_back(pii{v[i][0], v[i][0]*2});
vis1[v[i][0]*2] = 1;
}
}
}
int a = 0, tmp=-1;
for(int i = 0; i < v[1].size(); i++){
if(!vis1[v[1][i]]){
if(a%2==0){
tmp = v[1][i];
}else {
m.push_back(pii{tmp, v[1][i]});
}
a++;
}
}
printf("%d\n", m.size());
for(int i = 0; i < m.size(); i++){
printf("%d %d\n", m[i].first, m[i].second);
}
}
return ;
}
int main(){
init();
cf();
return 0;
}
上一篇: shiro过滤器
下一篇: Flask——过滤器
推荐阅读
-
2020牛客多校第3场:[Points Construction Problem + 思维题+构造]
-
2020暑假牛客多校第九场 K The Flee Plan of Groundhog (树形结构/思维)
-
2020牛客暑期多校训练营(第四场)F题
-
2020牛客暑期多校第一场J题
-
2020牛客暑期多校第四场 H - Harder Gcd Problem(思维/构造)
-
2018牛客多校第四场J题 Hash Function(思维+并查集)
-
牛客暑假多校2020第四场H题, 思维题
-
2020牛客暑期多校 第四场H-Harder Gcd Problem(思维,gcd)
-
2020牛客多校第二场(G题)Greater and Greater
-
2020牛客多校第二场B题Boundary