渝北网站制作公司企业网站推广

渝北网站制作,公司企业网站推广,葫芦岛长城建设公司网站,wordpress 3.5 下载【题目链接】 ybt 1640#xff1a;C Looooops LOJ 10218. 「一本通 6.4 练习 4」C Looooops 【题目考点】 1. 线性同余方程 相关知识见 【模板】洛谷 P1082 [NOIP 2012 提高组] 同余方程 【解题思路】 在C或C的kkk位存储系统#xff0c;可以存储[0,2k−1][0, 2^k-1][0,…【题目链接】ybt 1640C LooooopsLOJ 10218. 「一本通 6.4 练习 4」C Looooops【题目考点】1. 线性同余方程相关知识见 【模板】洛谷 P1082 [NOIP 2012 提高组] 同余方程【解题思路】在C或C的k kk位存储系统可以存储[ 0 , 2 k − 1 ] [0, 2^k-1][0,2k−1]范围内的整数。如unsigned int类型的范围为[ 0 , 2 32 − 1 ] [0, 2^{32}-1][0,232−1]unsigned long long类型的范围为[ 0 , 2 64 − 1 ] [0, 2^{64}-1][0,264−1]。当变量的数值超出了该数据类型可以表示的范围会发生“自然溢出”变量在二进制下只会保留末k kk位在数值角度看相当于进行了m o d 2 k \bmod 2^kmod2k操作。for (variable A; variable ! B; variable C)该代码的意义为变量初值为A每次循环变量的值增加C当变量的值等于B时跳出循环。假设进行了x xx次循环则有A x C m o d 2 k B AxC \bmod 2^k BAxCmod2kB。或列成同余方程A x C ≡ B ( m o d 2 k ) AxC\equiv B \pmod{2^k}AxC≡B(mod2k)整理得C x ≡ B − A ( m o d 2 k ) Cx\equiv B-A \pmod{2^k}Cx≡B−A(mod2k)如果g c d ( C , 2 k ) ∣ ( B − A ) gcd(C, 2^k)\mid (B-A)gcd(C,2k)∣(B−A)则该方程有解通过扩展欧几里得算法求线性同余方程的解。-如果g c d ( C , 2 k ) ∤ ( B − A ) gcd(C, 2^k)\nmid (B-A)gcd(C,2k)∤(B−A)则该方程无解即无论进行几次循环变量的值都无法等于B BB输出FOREVER。【题解代码】解法1扩展欧几里得算法直接求解线性同余方程#includebits/stdc.husingnamespacestd;#defineN25#defineMOD(a,b)(((a)%(b)(b))%(b))typedeflonglongLL;voidexgcd(LL a,LL b,LLx,LLy,LLg){if(b0){x1,y0,ga;return;}exgcd(b,a%b,y,x,g);y-a/b*x;}intmain(){LL a,b,c,k,x,y,g;while(cinabck!(a0b0c0k0)){exgcd(c,1LLk,x,y,g);if((b-a)%g0)coutMOD(x*(b-a)/g,(1LLk)/g)endl;elsecoutFOREVERendl;}return0;}解法2先求乘法逆元再解线性同余方程#includebits/stdc.husingnamespacestd;#defineN25#defineMOD(a,b)(((a)%(b)(b))%(b))typedeflonglongLL;voidexgcd(LL a,LL b,LLx,LLy){if(b0){x1,y0;return;}exgcd(b,a%b,y,x);y-a/b*x;}LLgcd(LL a,LL b){if(b0)returna;returngcd(b,a%b);}LLinv(LL a,LL m){LL x,y;exgcd(a,m,x,y);returnMOD(x,m);}intmain(){LL a,b,c,k,x,y,g;while(cinabck!(a0b0c0k0)){ggcd(c,1LLk);if((b-a)%g0)coutMOD((b-a)/g*inv(c,1LLk),(1LLk)/g)endl;elsecoutFOREVERendl;}return0;}