参考资料：

十个利用矩阵乘法解决的经典题目

题目链接

题意：求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

思路：先用扩展欧几里得算法（excrt）解一般同余方程求出一个特解R,然后通解R' = R + k * LCM(a1..am)

题目链接

题意：给出k个方程，形式为 x==r1,求最小的正数x，无解输出-1.

思路：首先很容易让人联想到crt.

然而crt的使用条件是，所有的m(也就是这道题中的a)两两互质，这道题并不满足，因此不能使用crt.

题目链接：

**题意：**人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一

天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日

题目链接

题意：给出a,b,d，分别表示a,b两种刻度的砝码，以及要称量的物体重量为d.现在保证能称量出给定重量的物体，问两种砝码个数的和最小的时候，两种砝码分别有多少。如果有多组解，那么要求weight of(ax + by) 最小。

题目链接

题意： 问 循环for ( int i = a ; i !=b; i+=c)在% （2^k）的意义下循环了多少次。

思路：

一般的思路是：

列方程...

化成扩展欧几里得算法的形式。。。

根据裴蜀定理判断解是否存在...

题目链接

题意：两只青蛙初始在数轴的x,y点，单位时间内分别可以向右跳m米和n米，数轴是环型的，长度为L，问两只青蛙能否相遇，以及相遇时跳的次数。

思路：相遇就是同一时间在同一地点。

题目链接

题意：问ax+by=1的一组x>0的解，如果无解输出sorry.

思路：根据裴蜀定理， ax+by=1有解当且gcd(a,b)=1。

然后根据扩展欧几里得算法，我们可以得到一组x,y。需要注意的是，这只是其中一组解。

前置技能点：

维基百科_裴蜀定理（贝祖等式）

对任何[整数](https://zh.wikipedia.org/wiki/) ，  和它们的[最大公约 …

先放资料。

前置技能点：

剩余系

剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，**

这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系，

阅读更多