线性同余方程组的合并

类似于

$$a_ix\equiv b_i\mod m_i$$

的方程组就是线性同余方程组
根据同余的可加性,可令

$$x\equiv B \mod lcm(m_i) $$

所以答案就转化为了求B和lcm

$$a_1x \equiv b_1 \mod m1$$

$$x\equiv (b_1/\gcd(a_1,m_1))*(a_1^{-1}/gcd(a_1,m_1)) \mod (m_1/gcd(a_1,m_1))$$

$$x \equiv B_1 \mod m1$$

$$x=B_1+m_1*t $$此时的m1*t是未知的

带入第二个方程,并整理

$$a(B_1+m_1t) \equiv b_2 \mod m_2$$

$$am_1t \equiv b_2-aB_1 \mod m_2$$

解出t

$$t \equiv (b_2-aB_1)/gcd(am_1,m_2) * (am_1)^{-1}/gcd(am_1,m_2) \mod (m_2)/gcd(am_1,m_2)$$

把t带入

$$x=B_1+m_1*t $$

$$x\equiv B_2 \mod lcm(m_1,m_2) $$

$$x=B_2+lcm*t$$

再带入第三个方程即可向下合并

//返回一个b,m对 
pair<int, int> inner_congruence(const vector<int> &A,const vector<int> &B,const vector<int> &M)
{
	int x=0,m=1;
	for(int i-9;i<A.size();i++)
	{
		int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(a,M[i]);
		if(b%d!=0) return make_pair(0,-1); //无解
		
Read the rest

【矩阵快速幂】nth Term LightOJ – 1096

You have to find the nth term of the following function:

f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2)

     = 0, if(n ≤ 2)

Input
Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output
For each case, print the case number and f(n) modulo 10007.

Sample Input
Read the rest

【数学-贪心-末状态已知】问题集合

  • 蓝书 P4 分金币

https://vjudge.net/problem/UVA-11300

关于本题的“想一想为什么”:因为非齐次方程组的系数行列式为0,所以方程的解不唯一,所以最后一个方程没有贡献。

末态相同的题目,可以往方程组方向去想。最后可以往坐标的距离方面去靠。

  • 蓝书 P7 雕塑

本题第一个设想“有一个雕塑不会动”的证明:

设开始每个墓碑相差A,移动后每个墓碑相差M,M可以不相同,因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

$$A-X_1+X_2=M =>X_2=X_1-(A-M)$$

$$A-X_2+X_3=M =>X_3=X_1-2(A-M)$$

$$…$$

$$A-X_n+X_1=M =>X_n=X_1-n(A-M)$$

 

同样可以变成X1到各个数字的距离最小的问题,即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案,因为M仅仅是假设存在一个M使其满足末态,由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解… Read the rest