Bzoj题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3310
Uscao官网题目数据及题解：http://usaco.org/index.php?page=nov13problems
题目已经提示结果跟入座顺序无关，那么一次性把所有奶牛加进去（刚开始一直纠结x,y的取值，还以为是数论题，后来发现如果有解，那么sigma x*y<n），然后从前往后推一次，然后直接出答案。(O(n+k))
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 3000001
int f[MAXN],n,k,a,b,x,y;
int main() {
scanf("%d%d",&n,&k);
memset(f,0,sizeof(f));
while (k--) {
scanf("%d%d%d%d",&x,&y,&a,&b);
for (int i=0;i++<y;) {
f[(((a%n)*i)%n+b%n)%n]+=x;
}
}
for (int i=0;i<n;i++) {
if (f[i]>1) {
f[i+1]+=f[i]-1;
f[i]=1;
}
}
f[0]+=f[n];
for (int i=0;i<n;i++) {
if (f[i]>1) {
f[i+1]+=f[i]-1;
f[i]=1;
}
}
for (int i=0;i<n;i++) if (!f[i]) {
printf("%d\n",i);
break;
}
return 0;
}
