bzoj#P1963. 最小和

最小和

题目描述

FF 是一个整数 \to 整数的函数,换句话说,FF 在所有整数上有定义,对于任何一个整数 xxF(x)F(x) 是一个整数。现在给一个整数 cc。如果对于所有的整数 xx,下面这个等式都满足,那么 FF 就被叫做 cbeautifulc-\text{beautiful} 函数。

F(2F(x)x+1)=F(x)+cF(2 \cdot F(x)-x+1)=F(x)+c

输出下面这个式子当 FF 是一个 cbeautifulc-\text{beautiful} 函数的时候可能的最小值。

i=0n1F(xi)yi\sum^{n-1}_{i=0}\left|F(x_i)-y_i\right|

使用下列方法生成 xix_iyiy_i

x[0] = xzero
x[i] = (x[i - 1] * xprod + xadd) % xmod
y[0] = yzero
y[i] = (y[i - 1] * yprod - yadd) % ymod

输入格式

输入共一行,1010 个正整数,依次为 c,n,xzero,xprod,xadd,xmod,yzero,yprod,yadd,ymodc,n,xzero,xprod,xadd,xmod,yzero,yprod,yadd,ymod

输出格式

输出共一行,为所求的最小值。

4 10 0 1 1 456 1 1 1 456
5

数据规模与约定

对于 100%100\% 的数据,1c161 \le c \le 161n1041 \le n \le 10^41xmod,ymod1091 \le xmod,ymod \le 10^90xzero,xprod,xadd0 \le xzero,xprod,xadd