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

浏览数：29 / 时间：2015年06月11日

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;
}

Codeforces Round #257 (Div. 2) E题：Jzzhu and Apples 模拟,,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

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