首页 > ACM题库 > HDU-杭电 > HDU 2769-HOJ-Disgruntled Judge[解题报告]C++
2014
02-14

HDU 2769-HOJ-Disgruntled Judge[解题报告]C++

Disgruntled Judge

问题描述 :

Once upon a time, there was an nwerc judge with a tendency to create slightly too hard problems. As a result, his problems were never solved. As you can image, this made our judge somewhat frustrated. This year, this frustration has culminated, and he has decided that rather than spending a lot of time constructing a well-crafted problem, he will simply write some insanely hard problem statement and just generate some random input and output files. After all, why bother having proper test data if nobody is going to try the problem anyway?

Thus, the judge generates a testcase by simply letting the input be a random number, and letting the output be another random number. Formally, to generate the data set with T test cases, the judge generates 2T random numbers x1, …, x2T between 0 and 10000, and then writes T, followed by the sequence x1, x3, x5, …, x2T-1 to the input file, and the sequence x2, x4, x6, …, x2T to the output file.

The random number generator the judge uses is quite simple. He picks three numbers x1, a, and b between 0 and 10000 (inclusive), and then for i from 2 to 2T lets xi = (a ・ xi-1 + b) mod 10001.

You may have thought that such a poorly designed problem would not be used in a contest of such high standards as nwerc. Well, you were wrong.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line containing an integer n (0 ≤ n ≤ 10000): an input testcase.

The input file is guaranteed to be generated by the process described above.

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line containing an integer n (0 ≤ n ≤ 10000): an input testcase.

The input file is guaranteed to be generated by the process described above.

样例输入:

3
17
822
3014

样例输出:

9727
1918
4110

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int x[11000];

int mod;

void exgcd(int &d,int &x,int &y,int a,int b)
{
		if(!b)
					d=a,x=1,y=0;
						else
							exgcd(d,y,x,b,a%b),y-=x*(a/b);
}
int jud(int a,int b,int n)
{
	int i;
	for(i=1;i<n;i++)
	{
		if((((x[i]*a)%mod)*a+(a*b)%mod+b)%mod-x[i+1])
			return 0;
	}
	return 1;
}
int get(int a,int n)
{
	int aa=a+1,bb=(x[2]-(((a*a)%mod)*x[1])%mod+mod)%mod;
	int gcd,y,t;

	exgcd(gcd,t,y,aa,mod);






if(bb%gcd)
		return -1;





	t%=mod;
	t*=bb/gcd;t%=mod;
t=(t+mod)%mod;


	int i;
	for(i=0;i<gcd;i++)
	{
		if(jud(a,t,n))
			return t;
		t+=mod/gcd;
		t%=mod;
	}
	return -1;
}

int main()
{
	mod=10001;
	int n,i,j;


	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&x[i]);
	for(i=0;i<=10000;i++)
	{
		j=get(i,n);
		if(j>=0)
		{
//if((x[1]*i+j)%mod-9727)
//continue;
			for(int ii=1;ii<=n;ii++)
				printf("%d\n",(x[ii]*i+j)%mod);
//printf("%d\n%d\n",i,j);
			return 0;
		}
	}
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。