欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客暑假多校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;
}