pro：现在给定一个大小为N*M的巧克力，让你横着或者竖着切K刀，都是切的整数大小，而且不能切在相同的地方，求最大化其中最小的块。 (N，M，K<1e9)
sol：如果横着切X刀，竖着切Y刀，那么最小的面积=(N/(X+1))*(M/(Y+1))；一看这个公式知道是整数分块了，相同的部分合并。 需要保证X<N，Y<M；
#include<bits/stdc++.h> #define ll long long using namespace std; int N,M,K;ll ans=-1; int main() { scanf("%d%d%d",&N,&M,&K); K+=2; for(int i=1,j;i<=min(K-1,N);i=j+1){ j=N/(N/i);int p=j;if(p>=K) p=K-1; if(K-p>M) continue; ans=max(ans,1LL*(N/i)*(M/(K-p))); } printf("%lld\n",ans); return 0; }
pro：给定N，表示有数字1到N，如果不互质的两个数可以配对，现在问最多可以配对多少对。
sol：（我好菜啊，不会构造，没看题解不会做系列）。从小到大枚举大于2的素数p，把没有配对的 p的倍数抽出来，如果有num个，当num为偶数时，两两配对即可； 否则，其中一个不嫩配对，那么我们把2*p拿出来即可。 即是，这写被单出来的数字都有因子2，最后他们之间又可以配对。 这样可以保证最大化配对。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=200010; int vis[maxn],a[maxn],b[maxn],tot; int p[maxn],cnt,N,q[maxn],num; void getprime() { for(int i=2;i<=N;i++){ if(!vis[i]) p[++cnt]=i; for(int j=1;j<=cnt&&i*p[j]<=N;j++){ vis[i*p[j]]=1; if(!(i%p[j])) break; } } } int main() { scanf("%d",&N); if(N==1||N==2) return puts("0"),0; getprime(); rep(i,1,N) vis[i]=0; vis[1]=1; rep(i,2,cnt){ num=0; int pos=1; for(int j=p[i];j<=N;j+=p[i]) if(!vis[j]) q[++num]=j; if(num&1) swap(q[1],q[2]),pos=2; rep(j,pos,num){ tot++; a[tot]=q[j]; b[tot]=q[++j]; vis[a[tot]]=vis[b[tot]]=1; } } num=0; int pos=1; for(int j=p[1];j<=N;j+=p[1]) if(!vis[j]) q[++num]=j; if(num&1) swap(q[1],q[2]),pos=2; rep(j,pos,num){ tot++; a[tot]=q[j]; b[tot]=q[++j]; vis[a[tot]]=vis[b[tot]]=1; } printf("%d\n",tot); rep(i,1,tot) printf("%d %d\n",a[i],b[i]); return 0; }
Codeforces Round #257 (Div. 1简单题解)
原文：https://www.cnblogs.com/hua-dong/p/10459098.html