参考资料： 十个利用矩阵乘法解决的经典题目

题目链接 题意：求在小于等于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) 注意一些特殊情况，如果无解输出0，如果n小于最小的正整数的R也输出0， 否则答案为(n-R)/M + 1 /* *********************************************** Author :111qqz …

题目链接 题意：给出k个方程，形式为 x==r1,求最小的正数x，无解输出-1. 思路：首先很容易让人联想到crt. 然而crt的使用条件是，所有的m(也就是这道题中的a)两两互质，这道题并不满足，因此不能使用crt. X mod m1=r1 X mod m2=r2 ... ... ... X mod mn=rn 首先，我们看两个式子的情况 X mod m1=r1……………………………………………………………(1) X mod m2=r2……………………………………………………………(2) 则有 X=m1k1+r1………………………………………………………………() X=m2k2+r2 那么 m1k1+r1=m2k2+r2 整理， …

题目链接： **题意：**人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一 天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日 期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少 再过多少天后三个峰值同时出现。 思路：解一个线性同余方程。crt的模板题。 关于crt的讲解：中国剩余定理学习笔记 几年前就A过了，现在重新写题解复习一下。 /* *********************************************** Author :111qqz Created Time …

题目链接 题意：给出a,b,d，分别表示a,b两种刻度的砝码，以及要称量的物体重量为d.现在保证能称量出给定重量的物体，问两种砝码个数的和最小的时候，两种砝码分别有多少。如果有多组解，那么要求weight of(ax + by) 最小。 思路：求特解直接扩展欧几里得... 关键是怎么找到绝对值和最小的。。 我就是两个方向跑了下。。。 一开始因为把weight of (ax+by) （求得还是绝对值最小）理解成了 ax+by最小。。导致WA了半天。。。。sigh.... /* *********************************************** Author :111qqz Created Time :Thu …

题目链接 题意： 问 循环for ( int i = a ; i !=b; i+=c)在% （2^k）的意义下循环了多少次。 思路： 一般的思路是： 列方程... 化成扩展欧几里得算法的形式。。。 根据裴蜀定理判断解是否存在... 然后用对用扩展欧几里得算法求出的X,Y按照题目要求调整。 /* *********************************************** Author :111qqz Created Time :Thu 13 Oct 2016 03:57:06 PM CST File Name :code/poj/2115.cpp …

题目链接 题意：两只青蛙初始在数轴的x,y点，单位时间内分别可以向右跳m米和n米，数轴是环型的，长度为L，问两只青蛙能否相遇，以及相遇时跳的次数。 思路：相遇就是同一时间在同一地点。  那么有方程 x+ Cm = y + Cn + k*L 其中C为跳的次数，k为之间差了L的个数（可以理解为被套圈的圈数） 化简得到 C(m-n) + K*L = y-x. 根据裴蜀定理，该方程有解，当且仅当y-x是gcd(m-n,L)的倍数。 然后根据扩展欧几里得算法，需要注意的是其中可能有负数。 如果a是负数， …

题目链接 题意：问ax+by=1的一组x>0的解，如果无解输出sorry. 思路：根据裴蜀定理， ax+by=1有解当且gcd(a,b)=1。 然后根据扩展欧几里得算法，我们可以得到一组x,y。需要注意的是，这只是其中一组解。 x,y的通解为：**(x+kgx , y-kgy ） 其中：gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 ** /* *********************************************** Author :111qqz Created Time :Wed 12 Oct 2016 07:30:20 PM CST File Name …

前置技能点： 维基百科_裴蜀定理（贝祖等式） 对任何[整数](https://zh.wikipedia.org/wiki/) ，  和它们的[最大公约 …

先放资料。 前置技能点： 剩余系 剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，** 这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系， 每个数称为相应类的代表元。 当m=10（偶数）时候，则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系 {-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系 {-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小 {1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系 简化剩余系:在每个剩余类选取至1个与m …