Codeforces Round #257 (Div. 1) C
Codeforces Round #257 (Div. 1) E
CF450E
|
C. Jzzhu and Apples
time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputJzzhu 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 Input
9 Output
3 Input
2 Output
0 |
题意：有N个苹果，编号为1~N。现要将苹果组成若干对，每对苹果最小公约数不为1。求最多能分成多少对，输出各对的组成。
题解：先筛素数，然后搞。
首先我们怕的是乱选了两个数组成了公约数不为1的一对，但是这导致了总对数减少（这两个数分别被别的数需要，它们组成一对了不是最优解）。为了防止这种情况，我们要想办法让总对数不会减少。
我们发现2的倍数们非常碉炸，任意2个就能组成1对，所以我们先弄其他的数，最后再搞2的倍数。
我们发现一个质数x的1倍、2倍、3倍、……？倍中未使用的数组成的集合，也可以任意两两组合，但是如果在1~n之间，这个集合的元素个数是奇数，就会多一个。为了不造成多余的影响，我们把2*x作为多出来的一个，扔到2的倍数中去。这样，各种集合的多出来的一个，肯定能找到配对。把我们使用的数标记一下，防止搞其他质数的时候重复用一个数。
先搞完3到小于等于(N/2)的质数（大于N/2，它的倍数的集合就只有它自己了，没法玩），然后搞2的倍数，把之前扔进来的2*x们和其他2*y（y是合数）组成一个大集合，两两配对，最后再多出来一个也没办法了，这已经是最多的配对了。
解不唯一，我们这样搞肯定能找到最多的对数，碉炸。
代码：
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12 using namespace std; 13 #define ll long long 14 #define usll unsigned ll 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define minf(array) memset(array, 0x3f, sizeof(array)) 17 #define REP(i,n) for(i=0;i<(n);i++) 18 #define FOR(i,x,n) for(i=(x);i<=(n);i++) 19 #define RD(x) scanf("%d",&x) 20 #define RD2(x,y) scanf("%d%d",&x,&y) 21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 22 #define WN(x) prllf("%d\n",x); 23 #define RE freopen("D.in","r",stdin) 24 #define WE freopen("1biao.out","w",stdout) 25 #define mp make_pair 26 #define pb push_back 27 28 const long N = 100001; 29 int prime[N],pn = 0; 30 bool isnp[N]; 31 void shai() { 32 int i,j; 33 memset(prime,0,sizeof(prime)); 34 memset(isnp,0,sizeof(isnp)); 35 isnp[0]=1,isnp[1]=1; 36 pn=0; 37 for(i = 2 ; i < N ; i ++) { 38 if(! isnp[i]) 39 prime[pn ++]=i; 40 //关键处1 41 for(j = 0 ; j < pn && i * prime[j] < N ; j ++) { 42 isnp[i * prime[j]] = 1; 43 if( !(i % prime[j] ) ) //关键处2 44 break; 45 } 46 } 47 } 48 49 int n; 50 vector<int>a,a2; 51 vector<pair<int,int> >v; 52 bool used[N]; 53 int main() { 54 int i,j,k; 55 int l,r,mid; 56 int pre; 57 int ans; 58 shai(); 59 while(scanf("%d",&n)!=EOF) { 60 ans=0; 61 v.clear(); 62 a2.clear(); 63 memset(used,0,sizeof(used)); 64 65 for(i=1; prime[i]<=n/2; i++) { 66 a.clear(); 67 a.pb(prime[i]); 68 for(j=3*prime[i]; j<=n; j+=prime[i]) if(!used[j]) a.pb(j); 69 if(a.size()%2==0) a2.pb(2*prime[i]); 70 else a.pb(2*prime[i]); 71 int maxj=a.size(); 72 for(j=0; j+1<maxj; j+=2) { 73 v.pb(mp(a[j],a[j+1])); 74 used[a[j]]=1; 75 used[a[j+1]]=1; 76 } 77 } 78 79 if(n>=2)a2.pb(2); 80 if(n>=4)a2.pb(4); 81 for(i=4; i+i<=n; i++) { 82 if(!used[i+i] && isnp[i]) a2.pb(i+i); 83 } 84 int maxi=a2.size(); 85 for(i=0; i+1<maxi; i+=2) v.pb(mp(a2[i],a2[i+1])); 86 printf("%d\n",v.size()); 87 maxi=v.size(); 88 REP(i,maxi) printf("%d %d\n",v[i].first,v[i].second); 89 } 90 return 0; 91 }