#P1963. 最小和

最小和

题目描述

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

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

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

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

使用下列方法生成 xix_i 和 yiy_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\% 的数据,1≤c≤161 \le c \le 16,1≤n≤1041 \le n \le 10^4,1≤xmod,ymod≤1091 \le xmod,ymod \le 10^9,0≤xzero,xprod,xadd0 \le xzero,xprod,xadd。