4895: 项链分赃（增强版）
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 277 Solved: 211
[ Submit ][ Status ][ Discuss ]
Description
你和你的1个同伙偷了一串长度为n的项链，它上面有m种颜色的珠子，我们假设项链为链状的，并且每一颗珠子都是随机分布，现在我想知道，对于给定的n，m你在最坏情况下最少需要切多少刀 才能使得你们可以通过每人获得一些切完之后的项链，并且满足每个人得到的每种宝石的数量刚好相同，我们假设珠子的数目一定是偶数。也就是说对于每种情况都一定存在一种解决方案。然而这才是这个问题的真正形式。Input
输入一行2个整数n，m意义如上所述。n,m<=1000000000Output
输出1行，表示在最坏情况下需要多少刀。Sample Input
1000 5Sample Output
5 【HINT】 事实上我们发现，只要我们给队友一刀就能解决了。试证明
一条n个珠宝的项链，每个珠宝有一个颜色，一共m种颜色。每种颜色均有偶数个珠宝。
现在切若干刀分成若干段，将一些段给A另一些给B。
使A和B每种颜色获得的珠宝数相同。
试证明至多m刀即可。
地球问题
基本是参考原题解的。
假设地球是一个完美的球体，而且气温和气压的变化是连续的，那么地球上一定存在一对相对的点气温和气压都相等。
我们来考虑证明吧。
假设你和你的女朋友都绕赤道走了半圈，且时刻保持你们两个所处的位置相对。
我们把赤道上气温气压的图像画出来，大概是这个样子的： 
我们知道气压的连续变化的。
然后你发现两人转半圈，且位置时刻相对，最终交换位置。
也就是你的气压从x变成了y，而你女友的气压从y变成了x。
那么无论多曲折，因为变化连续必定有交点。
也就是说同一条弧上存在相对点气压相等。 
对于每个类似赤道的弧，你都能得到这样的两点气压相同。
现在假设你和你的女朋友在赤道相对的位置且气压相同。
然后像图上这样走。 
这个过程中，你们的气压时刻相同，最后又会交换位置。
那么，你的初始气温是x，你的女朋友初始气温是y，最终你变成y而你女朋友变成x。
与气压一样，你们在某个点上气温一定会相同。
那么，总有一个(x,y,z)，和(-x,-y,-z)的气温与气压都相等。
现在呢，原来的项链是一堆离散的点。 
我们将它变成连续的，即可以在实数位置动刀。一个人可以获得实数个某颜色。 
只要能找到实数解，当然就能找到整数解。
这个很容易证明，因为总和是整数，一个合法解某人得到的某颜色一定是整数，即使存在实数段，可以通过改变刀的位置保持合法不变，然后能找到整数解。
现在让我们来说明新问题有解吧！
首先我们回忆一下地球问题告诉了我们什么呢？
地球是一个三维空间，每个位置有气温和气压，气温和气压是连续变化的。
我们设函数f(x,y,z)=(p,q)表示(x,y,z)的气温是p气压是q。
那么存在f(x,y,z)=f(-x,-y,-z)。
这就是地球问题给我们的结论。
接下来，我们证明m=2时项链切了两刀一定有解。
我们设项链长度为1，你用两刀将项链切成了三段，长度分别是x^2,y^2和z^2。
那么有x^2+y^2+z^2=1。
你可能发现了这就是一个球的方程式。
一组解(x,y,z)的含义是什么？对于每一段，它是带符号的。我们认为正表示给了第一个海盗，负表示给了第二个海盗。
同样的我们给它设置一个函数f(x,y,z)=(p,q)，p表示第一个海盗获得的第一种颜色的数量，q表示第一个海盗获得的第二种颜色的数量。
可以发现，它的变化的连续的！
接着，根据地球问题得到的结论。
存在f(x,y,z)=f(-x,-y,-z)。
回忆含义，全部取反相当于两个海盗交换了所拥有的颜色段。
而f(x,y,z)=f(-x,-y,-z)也就说明两个海盗每种颜色拥有数量都相同！
因此我们证明了m=2的情况。
m无论多大，都可以用m+1维地球的思路来解释不用超过m刀即可完成分赃。
证毕？
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(void)
{
int n, m;
while(scanf("%d%d", &n, &m)!=EOF)
printf("%d\n", min((n-1), m));
return 0;
}