网站建设经费预算包括哪些天元建设集团第一有限公司
张小明 2026/1/12 18:12:18
网站建设经费预算包括哪些,天元建设集团第一有限公司,智联招聘官方网,企业网站 php 免费【题目链接】
ybt 1635#xff1a;【例 5】Strange Way to Express Integers LOJ #10213. 「一本通 6.4 例 5」Strange Way to Express Integers
【题目考点】
1. 扩展中国剩余定理
相关知识见#xff1a;洛谷 P4777 【模板】扩展中国剩余定理#xff08;EXCRT#xff…【题目链接】ybt 1635【例 5】Strange Way to Express IntegersLOJ #10213. 「一本通 6.4 例 5」Strange Way to Express Integers【题目考点】1. 扩展中国剩余定理相关知识见洛谷 P4777 【模板】扩展中国剩余定理EXCRT【解题思路】本题没有指明同余方程组的模数m 1 , m 2 , . . . , m n m_1, m_2, ..., m_nm1,m2,...,mn互质因此不能使用中国剩余定理需要使用扩展中国剩余定理。本题是扩展中国剩余定理的模板题要求对多组数据求解。相关知识及解题方法见洛谷 P4777 【模板】扩展中国剩余定理EXCRT【题解代码】解法1扩展中国剩余定理#includebits/stdc.husingnamespacestd;#defineN100005#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;}LLexCRT(LL*a,LL*m,LL n)//x≡a[i] (mod m[i]){LL caa[1],cmm[1],x,y,g,lcm;for(inti2;in;i){exgcd(cm,m[i],x,y,g);if((a[i]-ca)%g!0)return-1;//无解时返回-1lcmcm/g*m[i];//lcm(cm, m[i])caMOD(MOD((__int128)(a[i]-ca)/g*x,m[i]/g)*cmca,lcm);//此处不能使用函数mod因为会把int128类型转为LL类型有精度丢失cmlcm;}returnca;}intmain(){LL a[N],m[N],n;while(cinn){for(inti1;in;i)cinm[i]a[i];coutexCRT(a,m,n)\n;}return0;}