上海婚恋网站排名,动漫做的游戏 迅雷下载网站,wordpress 修改数据库,建筑网站的研究背景与意义正题 大意
有n个野人#xff0c;每个野人有一个初始山洞CiCi#xff0c;每次向前移动距离PiPi#xff0c;寿命LiLi#xff0c;如果野人走到了最后一个山洞那么继续就好回到第一个山洞#xff0c;求至少多少个山洞才可以让野人们不会发生冲突。 解题思路
我们可以枚举答…正题 大意
有n个野人每个野人有一个初始山洞CiCiC_i每次向前移动距离PiPiP_i寿命LiLiL_i如果野人走到了最后一个山洞那么继续就好回到第一个山洞求至少多少个山洞才可以让野人们不会发生冲突。 解题思路
我们可以枚举答案然后我们要判断是否冲突我们可以枚举两个野人然后列出式子
CiPix≡CjPjx(mod l)CiPix≡CjPjx(modl)
C_i+P_ix\equiv C_j+P_jx(mod\ \ l) 如果这个式子有解且最小解 xLi/LjxLi/Ljx那么就会有冲突。 我们先把式子转换一下 (Ci−Cj)(Pi−Pj)x≡0(mod l)(Ci−Cj)(Pi−Pj)x≡0(modl)
(C_i-C_j)+(P_i-P_j)x\equiv 0(mod\ \ l) (Ci−Cj)(Pi−Pj)xly(Ci−Cj)(Pi−Pj)xly
(C_i-C_j)+(P_i-P_j)x=ly (Pi−Pj)x−ly(Ci−Cj)(Pi−Pj)x−ly(Ci−Cj)
(P_i-P_j)x-ly=(C_i-C_j) 然后我们进行扩欧代码
#includecstdio
#includealgorithm
using namespace std;
int x,y,n,c[16],p[16],l[16],maxc,d,A,B,g;
bool flag;
int gcd(int a,int b)//同余
{if (b0){x1;y0;return a;}dgcd(b,a%b);int kx;xy;yk-a/b*y;return d;
}
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d%d%d,c[i],p[i],l[i]);maxcmax(maxc,c[i]);}while (1){flagfalse;for (int i1;in;i){for (int ji1;jn;j){Ac[i]-c[j];Bp[j]-p[i];if (B0){A-A;B-B;//取反因为是 -ly}dgcd(B,maxc);gmaxc/d;g((x*(A/d))%gg)%g;//最小解if (!(A%d)gl[i]gl[j])//判断{flagtrue;break;}}if (flag) break;}if (!flag) break;maxc;//枚举}printf(%d,maxc);
}
