北京网站建设需要多少钱,铁道部建设司网站,aspcms网站打开慢,wordpress微信绑定域名文章目录 作用证明AcWing 204. 表达整数的奇怪方式CODE 作用
用于求模数两两互质的线性同余方程组#xff0c;若不互质则不存在解。 《孙子算经》中有这样一个问题#xff1a;“今有物不知其数#xff0c;三三数之剩二#xff0c;五五数之剩三#xff0c;七七数之剩二若不互质则不存在解。 《孙子算经》中有这样一个问题“今有物不知其数三三数之剩二五五数之剩三七七数之剩二问物几何这就是经典的剩余定理问题也是我们小学题目三个三个数余二五个五个数余三七个七个数余二求这个数是几 { x ≡ 2 ( m o d 3 ) x ≡ 3 ( m o d 5 ) x ≡ 2 ( m o d 7 ) \left\{ \begin{array}{c} x ≡ 2\ (mod\ 3)\\ x ≡ 3\ (mod\ 5)\\ x ≡ 2\ (mod\ 7) \end{array} \right. ⎩ ⎨ ⎧x≡2 (mod 3)x≡3 (mod 5)x≡2 (mod 7)
更多详细介绍请看VCR: 中国剩余定理的由来与求解过程。 证明
请看题解https://www.acwing.com/solution/content/3539/ 和https://www.acwing.com/solution/content/23099/
思路就是先读入一个式子然后以这个式子为基准再读入一个式子找他们的通解将式子更新为他们的通解然后再读入继续找通解直到读完。
证明过程太纷繁复杂蒟蒻的我选择直接记公式 每次更新完式子变为 x k ∗ l c m ( a 1 , a 2 ) k 1 ∗ a 1 m 1 k ∗ a 0 m 0 x k * lcm(a_1, a_2) k_1 * a_1 m_1 k * a_0 m_0 xk∗lcm(a1,a2)k1∗a1m1k∗a0m0 所以我们需要更新 a 1 l c m ( a 1 , a 2 ) a 1 / d ∗ a 2 m 1 k 1 ∗ a 1 m 1 a_1 lcm(a_1, a_2) a_1 / d * a_2\\ m_1 k_1 * a_1 m_1 a1lcm(a1,a2)a1/d∗a2m1k1∗a1m1 在这之前我们需要将 k 1 k_1 k1 的值更新出来 k 1 ( ( m 2 − m 1 ) / d ∗ k 1 ) % ( a 2 / d ) k_1 ((m2 - m1) / d * k_1) \%\ (a2 / d) k1((m2−m1)/d∗k1)% (a2/d) 就是求最小公倍数然后取模求最小解。 到最后我们求的 m 1 m_1 m1 即为 x x x求个模找最小即可。 AcWing 204. 表达整数的奇怪方式
题目链接https://www.acwing.com/activity/content/problem/content/948/ CODE
#include iostream
#include cstring
#include algorithm
#include cmathusing namespace std;typedef long long ll; // 定义长整型别名为ll// 扩展欧几里得算法求解ax by gcd(a, b)的一组解
ll exgcd(ll a, ll b, ll x, ll y){if(b 0){ // 当b为0时x为1y为0x 1, y 0;return a; // 返回最大公约数}ll x1, y1;ll d exgcd(b, a % b, x1, y1); // 递归求解x y1, y x1 - a / b * y1; // 更新x和yreturn d; // 返回最大公约数
}int main(){int n; // 定义整型变量nscanf(%d, n); // 输入nll a1, m1, x 0; // 定义长整型变量a1, m1, x并初始化x为0cin a1 m1; // 输入a1和m1for(int i 0; i n - 1; i){ll a2, m2, k1, k2; // 定义长整型变量a2, m2, k1, k2cin a2 m2; // 输入a2和m2ll d exgcd(a1, a2, k1, k2); // 调用扩展欧几里得算法求解最大公约数if((m1 - m2) % d){ // 如果(m1 - m2)不能被d整除x -1; // x赋值为-1break; // 跳出循环}k1 k1 * (m2 - m1) / d; // 更新k1ll t abs(a2 / d); // 定义长整型变量t并赋值为a2/d的绝对值k1 (k1 % t t) % t; // 更新k1m1 k1 * a1 m1; // 更新m1a1 abs(a1 * a2 / d); // 更新a1}if(x ! -1) x (m1 % a1 a1) % a1; // 如果x不等于-1则更新xcout x endl; // 输出x
}真的nm太抽象了吧这玩意儿是人学的我选择直接背以我的水平考到了也做不出来。
