1374.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1374 on 2005-11-12 at 00:16:57 */ 
#include <cstdio>

class Step {
	int s;
	int t;
public:
	int n;
	int a;
	void forward();
	void init(int, int);
};
void Step::forward() {
	s = (78901 + 31 * s) % 699037;
	t = (23456 + 64 * t) % 2097151;
	a = (s % 100 + 1) * (t % 100 + 1);
	n++;
}
void Step::init(int p, int q) {
	s = p;
	t = q;
	a = (s % 100 + 1) * (t % 100 + 1);
	n = 0;
}

int main()
{
	Step begin, end;
	int sum, s, m, N, M;
	int min, T, t, i;
	
	while(scanf("%d", &T) == 1) {
		for(t = 0; t < T; t++) {
			scanf("%d %d %d %d", &s, &m, &N, &M);
			begin.init(s, m);
			end.init(s, m);
			sum = end.a;
			min = N;
			for(i = 0; i <= N; i++) {
				while(sum > M) {
					if(min > end.n - begin.n) {
						min = end.n - begin.n;
					}
					sum -= begin.a;
					begin.forward();
				}
				end.forward();
				sum += end.a;
			}
			printf("%d\n", min);
		}
	}
	
	return 0;
}