【题目描述】 陶陶为了给一道平面几何题出数据，需要产生 N 个点(x[i],y[i])。已知 x,y 是由伪随机函数顺序产生，即： X[i+1] = (X[i]*Ax+Bx+i) mod Cx (X[1], Ax,Bx,Cx 是事先给定的） Y[i+1] = (Y[i]*Ay+By+i) mod Cy (Y[1], Ay,By,Cy 是事先给定的） 这样，就可以快速连续产生很多点坐标(X[i], Y[i])。 不幸的是，这样产生的点有可能有相同的，虽然这种几率很少，但严谨的陶陶不允许这种事发生。陶陶要求你帮助他解决最少要产生前多少项时，正好有 N 个不相同的点。 【输入格式】 第一行:一个整数 N 第二行：4 个整数 X[1]、 Ax、Bx、Cx 第三行：4 个整数 Y[1]、 Ay、By、Cy 【输出格式】 一个整数 M表示最少要连续产生 M 个点，正好有 N 个不相同的点。数据保证有答案。 【样例输入】 21 2 4 3 6 5 2 3 13 【样例输出】 24 【数据范围】 1<=N<=1,000,000, 其它所有数据都在[1…1,000,000,000]范围内。 【分析】 如果直接模拟会超时，故使用哈希优化。
const inf=1123357; var i,n,xi,ax,bx,cx,yi,ay,by,cy,m:qword; xx,yy,h:array[0..inf]of qword; procedure insert(x,y:qword); var t,i:qword; begin t:=(x*319+y*131) mod inf; while h[t]<>0 do begin i:=h[t]; if (xx[i]=x)and(yy[i]=y) then exit; t:=(t+1) mod inf; end; inc(m); xx[m]:=x;yy[m]:=y; h[t]:=m; end; begin readln(n); readln(xi,ax,bx,cx); readln(yi,ay,by,cy); fillchar(h,sizeof(h),0); m:=0; i:=1; insert(xi,yi); while m<n do begin xi:=(xi*ax+bx+i) mod cx; yi:=(yi*ay+by+i) mod cy; insert(xi,yi); inc(i); end; write(i); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533545.html
