第256章 扩展欧几里得算法，以及增强线段树 (第1/2页)

    “七八点钟？足够了。”熊磊率先表示赞同。

    朱达昌也点了点头，又说：“玩的太晚，两位老师也会不放心。”

    江寒笑问：“你们下午都这么有时间……今天不往回走了吗？”

    朱达昌回答：“高老师预定了火车卧铺，是夜里10点发车。”

    李山河点了点头，说：“要等8、9个小时的车，这么长时间，不玩点什么也太无聊了。”

    熊磊解释说：“我爸爸的车实在不能凑合了，准备买台全新的高尔夫6，明天就去4s店提车，所以只能晚一天回去。”

    江寒了然一笑，熊爸爸那辆二手车，动不动就趴窝，的确早该换换了。

    想了想，对李山河、朱达昌说：“我不一定能送你们上车，今晚我可能就得往回走了。”

    “这么急吗？好不容易来一趟松江，不好好玩一玩？”李山河问。

    江寒坦然点头，说：“我是坐方便车来的，别人什么时候往回走，我就什么时候跟回去，总不能让别人将就我吧？”

    其实要什么时候回去，还不是他一句话的事情？

    但夏雨菲明天有课……

    “诶？如果唱k的话，能不能让夏雨菲同学也来呀？”朱达昌突发奇想。

    “就是的，江寒，你和夏雨菲好像挺熟悉的，帮忙邀请一下呗。”李山河也力促。

    江寒一阵无语。

    别说，还真可以考虑一下。

    小媳妇这次出来，光跟着自己跑前跑后了，也没玩好……

    也不知道她有没有意愿出来散散心？

    江寒想了想，没把话说死：“好吧，比完赛我打电话问一声，能不能约出来，我可不敢保证哦。”

    听了江寒的话，其他人都十分期待，毕竟夏雨菲不光长得好看，在学校里也是有名的唱歌好听。

    但其实，江寒已经决定，顺便也叫苗清澜和关浩一声，愿意来的话，就一起热闹热闹。

    而且，出门在外的，指导教师们也不可能彻底放手，肯定都会跟着。

    这样的话，就不太好去一些环境太复杂的场所了……

    时间将到8点，赛场封锁就被解除，选手们再次鱼贯入场。

    其他流程和昨天大同小异。

    比赛正式开始。

    江寒拿到题之后，习惯性地全部浏览了一遍，然后从头开始做。

    今天的三道题，难度比Day1高多了。

    但说实话，并没有超过他的预计，都属于那种稍微花点心思就能解决的类型。

    第一题是同余方程。

    ：求关于x的同余方程ax≡1的最小正整数解。

    输入数据是两个正整数a和b，要求输出方程的最小正整数解x0。

    比如：输入3和10，输出就是7。

    数据范围：

    对于40%的数据，2≤b≤1000；

    对于60%的数据，2≤b≤50000000；

    对于100%的数据，2≤a≤2000000000，2≤b≤2000000000；

    输入的数据保证一定有解。

    江寒一打眼就看出来了，这是一道数论题。

    只要明白同余方程是怎么回事，就很容易理清思路。

    ，即ax的乘积除以b，余数为1。

    所以，对于任意给定的a、b，可以用穷举法暴力搜索，开始，每次递增1，很容易就能找出一个最小的x，使得方程成立。

    但因为a、b的取值范围特别巨大，这样做，会导致至少LimitExceeded，即时间超限）。

    要想得到全部分数，必须想办法缩减运算时间。

    如果能找到这个算式中隐藏的规律，问题自然迎刃而解。

    当然，这需要拥有一点数论功底，才能办得到。

    江寒先观察了一下方程。

    原式等价于ax-，因为k值可以为负数，所以又可以看做ax 。

    显而易见，a与b一定互质，所以原式可转化为，这里gcd表示两个整数的最大公约数……

    咦？

    这不就是扩展欧几里得的标准形式吗？

    这样就简单了啊！

    欧几里得算法也叫辗转相除法