在社保网站做调动,肇庆seo排名外包,网站能查到从哪里做的吗,wordpress卖邀请码链接Divisibility Part1 学习本节的基础#xff1a;任意个整数之间进行加、减、乘的混合运算之后的结果仍然是整数。之后将不申明地承认这句话的正确性并加以运用。 用一个不为 0 0 0的数去除另一个数所得的商却不一定是整数#xff08; a a a除 b b b#xff0c;写作 b a \frac…Divisibility Part1 学习本节的基础任意个整数之间进行加、减、乘的混合运算之后的结果仍然是整数。之后将不申明地承认这句话的正确性并加以运用。 用一个不为 0 0 0的数去除另一个数所得的商却不一定是整数 a a a除 b b b写作 b a \frac{b}{a} ab a a a除以 b b b写作 a b \frac{a}{b} ba所以我们需要引进整除的概念这节会对整除进行深入讨论。 接下来我们会给出定义且给出并证明定义引申出的定理最后对这些加以运用。
定义 1 1 1 设 a , b a,b a,b 是任意两个整数其中 b ≠ 0 b\neq0 b0如果存在一个整数 q q q使得等式 a b q ( 1 ) \qquad \qquad \qquad \qquad \qquad abq\qquad\qquad\qquad\qquad\qquad(1) abq(1) 成立我们就说 b b b 整除 a a a 或 a a a 被 b b b 整除记作 b ∣ a b|a b∣a此时我们把 b b b 叫做 a a a 的因数把 a a a 叫做 b b b 的倍数。
如果 ( 1 ) (1) (1) 里面的整数 q q q 不存在我们就说 b b b 不能整除 a a a记作 b ∤ a b \nmid a b∤a 。
接下来从定义出发证明一些关于整除的基本定理。
定理 1 1 1传递性 若 a a a 是 b b b 的倍数 b b b 是 c c c 的倍数则 a a a 是 c c c 的倍数也就是 b ∣ a , c ∣ b ⇒ a ∣ c b|a,c|b \Rarr a|c b∣a,c∣b⇒a∣c 证 由定义 1 1 1可知 b ∣ a , c ∣ b b|a,c|b b∣a,c∣b所以存在两个整数 a 1 , b 1 a_1,b_1 a1,b1使得 a a 1 b , b b 1 c aa_1b,\quad bb_1c aa1b,bb1c 成立因此 a ( a 1 b 1 ) c a(a_1b_1)c a(a1b1)c 又因为 a 1 , b 1 a_1,b_1 a1,b1 是整数所以 c ∣ a c|a c∣a。
定理 2 2 2 若 a , b a,b a,b 都是 m m m 的倍数那么 a ± b a\pm b a±b 也是 m m m 的倍数。
证 a , b a,b a,b 都是 m m m 的倍数所以存在两个整数 a 1 , b 1 a_1,b_1 a1,b1使得 a a 1 m , b b 1 m a a_1m,\quad bb_1m aa1m,bb1m a ± b a\pm b a±b 可以写作 a ± b ( a 1 ± b 1 ) m a\pm b (a_1\pm b_1)m a±b(a1±b1)m 因 a 1 ± b 1 a_1\pm b_1 a1±b1 是整数故 a ± b a\pm b a±b 是 m m m 的倍数。
同样的方法可以证明
定理 3 3 3 若 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an 都是 m m m 的倍数 q 1 , q 2 , ⋯ , q n q_1,q_2,\cdots,q_n q1,q2,⋯,qn 是任意 n n n 个整数则 q 1 a 1 q 2 a 2 ⋯ q n a n q_1a_1q_2a_2\cdotsq_na_n q1a1q2a2⋯qnan 是 m m m 的倍数。
证 因为 q 1 a 1 , q 2 a 2 , ⋯ , q n a n q_1a_1,q_2a_2,\cdots,q_na_n q1a1,q2a2,⋯,qnan 是 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an 的倍数 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an 是 m m m 的倍数由定理 1 1 1 可得 q 1 a 1 , q 2 a 2 , ⋯ , q n a n q_1a_1,q_2a_2,\cdots,q_na_n q1a1,q2a2,⋯,qnan 是 m m m 的倍数
由定理 2 2 2 得 q 1 a 1 q 2 a 2 ⋯ q n a n q_1a_1q_2a_2\cdotsq_na_n q1a1q2a2⋯qnan 是 m m m 的倍数。
定理 4 4 4带余除法 若 a , b a,b a,b 是任意两个整数其中 b 0 b0 b0则存在两个整数 q , r q,r q,r使得 a b q r , 0 ≤ r b ( 2 ) \qquad \qquad abqr,\quad \: 0\leq r b \qquad \qquad \qquad \qquad (2) abqr,0≤rb(2) 成立而且 q , r q,r q,r 是唯一的。
证 作整数序列 ⋯ , − 3 b , − 2 b , − b , 0 , b , 2 b , 3 b , ⋯ \cdots,-3b,-2b,-b,0,b,2b,3b,\cdots ⋯,−3b,−2b,−b,0,b,2b,3b,⋯ 那么 a a a 在这个序列的某相邻两项之间即存在一个整数 q q q使得 b q ≤ a b ( q 1 ) ( 3 ) \qquad \qquad \qquad bq\leq ab(q1)\qquad \qquad\qquad\qquad\quad (3) bq≤ab(q1)(3) 成立。令 r a − b q ra-bq ra−bq。代入 ( 3 ) (3) (3) 得 0 ≤ r b 0\leq rb 0≤rb 所以存在两个整数 q , r q,r q,r 使得 ( 2 ) (2) (2) 成立。
下面证明 q , r q,r q,r 的唯一性设 q , r q,r q,r 和 q 1 , r 1 q_1,r_1 q1,r1 是满足 ( 2 ) (2) (2) 的两对整数则 { a b q r ( 0 ≤ r b ) a b q 1 r 1 ( 0 ≤ r 1 b ) \begin{cases} abqr\quad(0\leq rb)\\ abq_1r_1\quad(0\leq r_1b) \end{cases} {abqr(0≤rb)abq1r1(0≤r1b) 联立得 b q r b q 1 r 1 bqrbq_1r_1 bqrbq1r1 移项 b ( q − q 1 ) r 1 − r b(q-q_1)r_1-r b(q−q1)r1−r 由于 r , r 1 r,r_1 r,r1 的值域都是 0 ≤ r b 0\leq rb 0≤rb所以二者相减的绝对值不超过 b b b。
即 b ∣ q − q 1 ∣ ∣ r 1 − r ∣ b|q-q_1||r_1-r| b∣q−q1∣∣r1−r∣ 解得 { q q 1 r r 1 \begin{cases} qq_1\\ rr_1 \end{cases} {qq1rr1 证毕。
整数的很多基本性质都可以从定理 ( 4 ) (4) (4) 引导出来本章最主要的内容都是在定理 ( 4 ) (4) (4) 的基础上建立。
定义 2 2 2 ( 2 ) (2) (2) 中的 q q q 叫做 a a a 被 b b b 除所得到的不完全商 r r r 叫做 a a a 的余数。 习题
一
证明定理 3 3 3。 二
证明 3 ∣ n ( n 1 ) ( 2 n 1 ) 3|n(n1)(2n1) 3∣n(n1)(2n1)其中 n n n 是任意整数。
题解 设 n 3 γ r n3\gammar n3γr ( 0 ≤ r 3 ) (0\leq r3) (0≤r3) 得
n ( n 1 ) ( 2 n 1 ) ( 3 γ r ) ( 3 γ r 1 ) ( 6 γ 2 r 1 ) n(n1)(2n1)(3\gammar)(3\gammar1)(6\gamma2r1) n(n1)(2n1)(3γr)(3γr1)(6γ2r1)
当 r 1 r1 r1那么 2 r 1 3 2r13 2r13 又 3 ∣ 6 γ , 3 ∣ 3 3|6\gamma,3|3 3∣6γ,3∣3 所以 3 ∣ ( 6 γ 2 r 1 ) 3|(6\gamma2r1) 3∣(6γ2r1)
所以 3 ∣ n ( n 1 ) ( 2 n 1 ) 3|n(n1)(2n1) 3∣n(n1)(2n1)。
当 r 2 r2 r2那么 r 1 3 r13 r13又 3 ∣ 3 γ , 3 ∣ 3 3|3\gamma,3|3 3∣3γ,3∣3 所以 3 ∣ ( 3 γ r 1 ) 3|(3\gammar1) 3∣(3γr1)
所以 3 ∣ n ( n 1 ) ( 2 n 1 ) 3|n(n1)(2n1) 3∣n(n1)(2n1)。
当 r 0 r0 r0 3 ∣ n 3|n 3∣n所以 3 ∣ n ( n 1 ) ( n 1 ) 3|n(n1)(n1) 3∣n(n1)(n1)。
证毕。 三
若 a x 0 b y 0 ax_0by_0 ax0by0 是形如 a x b y axby axby ( ( ( x , y x,y x,y 是任意整数 a , b a,b a,b 是两个不全为零的整数 ) ) ) 的数中最小的正整数证明 ( a x 0 b y 0 ) ∣ ( a x b y ) (ax_0by_0)|(axby) (ax0by0)∣(axby) 题解 设 a x b y q 1 ( a x 0 b y 0 ) r 1 ( 0 ≤ r 1 a x 0 b y 0 ) axbyq_1(ax_0by_0)r_1\quad(0\leq r_1ax_0by_0) axbyq1(ax0by0)r1(0≤r1ax0by0) 可得 r 1 a ( x − q 1 x 0 ) b ( y − q 1 y 0 ) r_1a(x-q_1x_0)b(y-q_1y_0) r1a(x−q1x0)b(y−q1y0) r 1 r_1 r1 满足 a x b y axby axby 的形式而 a x 0 b y 0 ax_0by_0 ax0by0 是形如 a x b y axby axby 的数中最小的正整数设 ( a x 0 b y 0 ) (ax_0by_0) (ax0by0)为 d d d。
所以 r 1 r_1 r1 是 d d d 的倍数设 r q 2 d rq_2d rq2d那么 a x b y q 1 d q 2 d axbyq_1dq_2d axbyq1dq2d。
显然 d ∣ ( a x b y ) d|(axby) d∣(axby)。
证毕。 四
若 a , b a,b a,b 是任意两个整数且 b ≠ 0 b\neq0 b0证明存在两个整数 s , t s,t s,t 使得 a b s t , ∣ t ∣ ≤ ∣ b ∣ 2 abst,\quad |t| \leq \frac{|b|}{2} abst,∣t∣≤2∣b∣ 成立并且当 b b b 是奇数的时候 s , t s,t s,t 是唯一存在的当 b b b 是偶数的时候结果如何
题解 由定理 4 4 4 可知对任意整数 a , b a,b a,b 都有 a q b r , 0 ≤ r ∣ b ∣ aqbr,\quad 0\leq r|b| aqbr,0≤r∣b∣ b b b 是正数
若 r ≤ b 2 r\leq\frac{b}{2} r≤2b则 s q , t r sq,tr sq,tr。
若 r ≥ b 2 r\geq \frac{b}{2} r≥2b 则 a ( q 1 ) b ( r − b ) a(q1)b(r-b) a(q1)b(r−b)显然 ∣ r − b ∣ b 2 |r-b|\frac{b}{2} ∣r−b∣2b s q 1 , t r − b sq1,tr-b sq1,tr−b b b b 是负数
若 r ≤ ∣ b 2 ∣ r\leq |\frac{b}{2}| r≤∣2b∣则 s q , t r sq,tr sq,tr。
若 r ≥ ∣ b 2 ∣ r\geq |\frac{b}{2}| r≥∣2b∣则 a ( q − 1 ) b ( r b ) a(q-1)b(rb) a(q−1)b(rb)显然 ∣ r b ∣ b 2 |rb|\frac{b}{2} ∣rb∣2b s q − 1 , t r b sq-1,trb sq−1,trb
当 b b b 为奇数 b 2 \frac{b}{2} 2b 向下取整不存在 r b 2 r\frac{b}{2} r2b s s s 只能取 q q q 或 q − 1 q-1 q−1 或 q 1 q1 q1 中的一个。
当 b b b 为偶数存在 r b 2 r\frac{b}{2} r2b所以当 r b 2 r\frac{b}{2} r2b时 s s s 既能取 q q q又能取 q − 1 q-1 q−1 或 q 1 q1 q1 。 五
检查一个整数 n n n 是否能被 3 3 3 整除。
题解
对于任意一个整数 n n n都可以写成 n a 0 × 1 0 0 a 1 × 1 0 1 ⋯ a n × 1 0 n na_0\times10^0a_1\times 10^1\dotsa_n\times10^n na0×100a1×101⋯an×10n 已知 1 0 i 10^i 10i 除以 3 3 3 的余数是 1 1 1所以 a i × 1 0 i a_i\times10^i ai×10i 除以 3 3 3 的余数等价于 a i a_i ai 除以 3 3 3 的余数。
那么 n n n 除以 3 3 3 的余数等价于 ∑ i 1 n a [ i ] \sum_{i1}^n a[i] ∑i1na[i] 除以 3 3 3 的余数。
所以 n n n 能被 3 3 3 整除等价于 ∑ i 1 n a [ i ] \sum_{i1}^{n}a[i] ∑i1na[i] 能被 3 3 3 整除。
证毕。 六
检查一个整数 n n n 是否能被 4 4 4 整除。
题解
对于任意一个整数 n n n都可以写成 n a 0 × 1 0 0 a 1 × 1 0 1 ⋯ a n × 1 0 n na_0\times10^0a_1\times 10^1\dotsa_n\times10^n na0×100a1×101⋯an×10n 已知 10 10 10 除以 4 4 4 的余数是 2 2 2已知 1 0 i 10^i 10i ( i ≥ 2 ) (i\geq2) (i≥2)除以 4 4 4 的余数是 0 0 0。
所以 n n n 除以 4 4 4 的余数取决于于 a 0 a 1 × 1 0 1 a_0a_1\times10^1 a0a1×101 除以 4 4 4 的余数。
如果 a 0 a 1 × 1 0 1 a_0a_1\times10^1 a0a1×101 除以 4 4 4 的余数是 0 0 0那么 n n n 能被 4 4 4 整除
换句话说 n n n 是否能被 4 4 4 整除取决于 n n n 的最后两位能否被 4 4 4 整除。
证毕。 七
检查一个整数 n n n 是否能被 6 6 6 整除。
题解
先检查最后一位数是否是偶数是否能被 2 2 2 整除再利用第五题的结论检查是否被 3 3 3 整除。
证毕。 八
检查一个整数 n n n 是否能被 7 7 7 整除。
同余做法
等价于直接判断 n m o d 7 n\:mod\:7 nmod7 是否为 0 0 0。
方法是将数字读入到字符串内然后从最高位开始对 7 7 7 取模然后乘以 10 10 10再下一位。
最后得到的数为 0 0 0就说明是 7 7 7 的倍数。
时间复杂度 O ( n ) O(n) O(n) n n n 代表数位个数。
这个方法是通用的如果时间复杂度允许 7 7 7 可以换成任意的数。
string s;
cin s;
int now 0;
for (int j 0; j s.size(); j) {now now * 10 (s[j] - 0);now % 7;
}
if(now 0) cout Yes endl;
else cout No endl;
