首页 > 代码库 > Codeforces Round #257 (Div. 2) E题：Jzzhu and Apples 模拟

Codeforces Round #257 (Div. 2) E题：Jzzhu and Apples 模拟

2024-07-13 17:22:04   223人阅读

E. Jzzhu and Apples
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jzzhu has picked n apples from his big apple tree. All the apples are numbered from 1 to n. Now he wants to sell them to an apple store.

Jzzhu will pack his apples into groups and then sell them. Each group must contain two apples, and the greatest common divisor of numbers of the apples in each group must be greater than 1. Of course, each apple can be part of at most one group.

Jzzhu wonders how to get the maximum possible number of groups. Can you help him?

Input

A single integer n (1?≤?n?≤?105), the number of the apples.

Output

The first line must contain a single integer m, representing the maximum number of groups he can get. Each of the next m lines must contain two integers — the numbers of apples in the current group.

If there are several optimal answers you can print any of them.

Sample test(s)
input
6
output
2
6 3
2 4
input
9
output
3
9 3
2 4
6 8
input
2
output
0

思路：这题刚开始确实想不到的。看了别人的解题报告才知道怎么搞。

因为只要最大公约数>1，所以偶数的组合肯定可以。但是奇数的就有点难搞了。如果用加倍的方法来组成一对的话那不是最多的情况。但是多加两位就是最多的情况了，这是前20名的代码中的做法。我没想明白。后面才感觉这得想到才行。因为奇数加两位之后为偶数的机率比较小，就不和偶数的组合情况重复了，然后又可以把奇数组合成一对。这太机智了。比赛的时候确实很难想出来。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define INF 1000000070000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int vis[100005],is[100005];
vector<pair<int,int> >v;
int main()
{
    int n,i,j;
    cin>>n;
    for(i=4;i<=n;i+=2)
        vis[i]=1;
    for(i=3;i<=n;i+=2)
    {
        if(!vis[i])
        {
            if(i*2>n) break;
            vector<int>a;
            for(j=i;j<=n;j+=2*i)
            {
                vis[j]=1;
                if(!is[j]) a.push_back(j),is[j]=1;
            }
            for(j=a.size()-1;j>0;j-=2)
            {
                v.push_back(make_pair(a[j],a[j-1]));
                is[a[j]]=is[a[j-1]]=1;
            }
            if(a.size()&1)
            {
                v.push_back(make_pair(a[0],a[0]*2));
                is[a[0]]=is[a[0]*2]=1;
            }
        }
    }
    if(n&1) n--;
    int x=0,y;
    for(i=n;i>0;i-=2)
    {
        if(is[i]) continue;
        if(!x) y=i,x=1;
        else x=0,v.push_back(make_pair(i,y));
    }
    printf("%d\n",v.size());
    for(i=0;i<v.size();i++)
        printf("%d %d\n",v[i].first,v[i].second);
    return 0;
}



联系
我们