CF449C Jzzhu and Apples

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

嘟嘟嘟

这道题正解是怎么对的其实我也不清楚，总之靠感性理解吧。

首先当然要把１到n / 2的素数都筛出来，因为两两能配对的数一定都是这些素数的倍数。这也就说明对于(n / 2, n]的素数，他们一定不能配对，所以就不用筛他们了。

筛完后我们考虑怎么配对，对于一个素数的所有倍数x _i ，他们任意两个都可以配对，但是可能配对完后得到的总配对数会减少。因此我们从最大的素数开始两两配对，感性理解就是越大的素数的倍数就越少，因此先尽量满足配对方案少的素数，然后再处理配对方案多的素数。

还有一点，就是当xi的倍数中没有配对的数是奇数个的时候，就会多出来一个，那么我们应该把哪一个丢出来呢？还是按照上面贪心的方法想：丢出来的数成功配对的可能性越大越好，即他的最小质因子越小越好。那么就应该丢掉2 * x _i 。

讲　完　了

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a, x) memset(a, x, sizeof(a))

 #define rg register

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 1e5 + ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar(x %  + '');

 }

 bool vis[maxn];

 struct Node

 {

   int x, y;

 }ans[maxn];

 int n, cnt = ;

 int prime[maxn], v[maxn];

 void init(int n)

 {

   for(int i = ; i <= n; ++i)

     {

       if(!v[i]) v[i] = i, prime[++prime[]] = i;

       for(int j = ; i * prime[j] <= n && j <= prime[]; ++j)

     {

       if(prime[j] > v[i]) break;

       v[i * prime[j]] = prime[j];

     }

     }

 }

 int main()

 {

   n = read();

   init(n >> );

   for(int i = prime[]; i; --i)

     {

       int flg = ; int las = ;

       for(int j = prime[i]; j <= n; j += prime[i]) if(!vis[j]) flg ^= ;  //记录奇偶

       for(int j = prime[i]; j <= n; j += prime[i])

     {

       if(j == (prime[i] << ) && flg && prime[i] != ) continue;

       if(las && !vis[j])

         {

           vis[j] = ;

           ans[++cnt] = (Node){las, j};

           las = ;

         }

       else if(!las && !vis[j]) las = j, vis[j] = ;

     }

     }

   write(cnt); enter;

   for(int i = ; i <= cnt; ++i) write(ans[i].x), space, write(ans[i].y), enter;

   return ;

 }