爱小说

第256章 扩展欧几里得算法,以及增强线段树

小说:重生学神有系统 作者:一碗酸梅汤 更新时间:2020-01-22 14:49
爱小说(www.ixs.cc)开通手机站了,手机用户可以登录 m.ixs.cc 进行阅读,效果更好哦!
  “七八点钟?足够了。”熊磊率先表示赞同。
  朱达昌也点了点头,又说:“玩的太晚,两位老师也会不放心。”
  江寒笑问:“你们下午都这么有时间……今天不往回走了吗?”
  朱达昌回答:“高老师预定了火车卧铺,是夜里10点发车。”
  李山河点了点头,说:“要等8、9个小时的车,这么长时间,不玩点什么也太无聊了。”
  熊磊解释说:“我爸爸的车实在不能凑合了,准备买台全新的高尔夫6,明天就去4s店提车,所以只能晚一天回去。”
  江寒了然一笑,熊爸爸那辆二手车,动不动就趴窝,的确早该换换了。
  想了想,对李山河、朱达昌说:“我不一定能送你们上车,今晚我可能就得往回走了。”
  “这么急吗?好不容易来一趟松江,不好好玩一玩?”李山河问。
  江寒坦然点头,说:“我是坐方便车来的,别人什么时候往回走,我就什么时候跟回去,总不能让别人将就我吧?”
  其实要什么时候回去,还不是他一句话的事情?
  但夏雨菲明天有课……
  “诶?如果唱k的话,能不能让夏雨菲同学也来呀?”朱达昌突发奇想。
  “就是的,江寒,你和夏雨菲好像挺熟悉的,帮忙邀请一下呗。”李山河也力促。
  江寒一阵无语。
  别说,还真可以考虑一下。
  小媳妇这次出来,光跟着自己跑前跑后了,也没玩好……
  也不知道她有没有意愿出来散散心?
  江寒想了想,没把话说死:“好吧,比完赛我打电话问一声,能不能约出来,我可不敢保证哦。”
  听了江寒的话,其他人都十分期待,毕竟夏雨菲不光长得好看,在学校里也是有名的唱歌好听。
  但其实,江寒已经决定,顺便也叫苗清澜和关浩一声,愿意来的话,就一起热闹热闹。
  而且,出门在外的,指导教师们也不可能彻底放手,肯定都会跟着。
  这样的话,就不太好去一些环境太复杂的场所了……
  时间将到8点,赛场封锁就被解除,选手们再次鱼贯入场。
  其他流程和昨天大同小异。
  8点30分,Day2比赛正式开始。
  江寒拿到题之后,习惯性地全部浏览了一遍,然后从头开始做。
  今天的三道题,难度比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;
  输入的数据保证一定有解。
  江寒一打眼就看出来了,这是一道数论题。
  只要明白同余方程是怎么回事,就很容易理清思路。
  原式可理解为axmodb=1,即ax的乘积除以b,余数为1。
  所以,对于任意给定的a、b,可以用穷举法暴力搜索,从x0=1开始,每次递增1,很容易就能找出一个最小的x,使得方程成立。
  但因为a、b的取值范围特别巨大,这样做,会导致至少4个点TLE。
  要想得到全部分数,必须想办法缩减运算时间。
  如果能找到这个算式中隐藏的规律,问题自然迎刃而解。
  当然,这需要拥有一点数论功底,才能办得到。
  江寒先观察了一下方程。
  原式等价于ax-kb=1,因为k值可以为负数,所以又可以看做ax+by=1。
  显而易见,a与b一定互质,所以原式可转化为ax+by=gcd,这里gcd表示两个整数的最大公约数……
  咦?
  这不就是扩展欧几里得的标准形式吗?
  这样就简单了啊!
  欧几里得算法也叫辗转相除法,用于求最大公约数,属于小学奥数常见内容。
  有个基本性质:gcd=gcd。
  而扩展欧几里德算法,则用来已知a,b,求解方程ax+by=gcd的解。
  根据数论中的相关定理,解是一定存在的。
  所以,这道题只要用上扩展欧几里德算法,就能很轻松找到一组x0、y0,使得等式成立。
  接下来,江寒根据算法,只花了五分钟,就编写出了对应的代码。
  其中的递归函数exgcd,就是扩展欧几里德算法的一种实现。
  用上了这种方法之后,编程难度大大降低,一共只用了10来行代码,就完成了解答。
  然后一调试……
  江寒就无语地发现,求解出来的x0,居然有时候会出现负值。
  这就不符合题意了。
  那么……为什么会产生这种情况呢?
  江寒想了想,拿过一张草稿纸,简单地推理了一下。
  在数学上,ax=1等价于ax%b=1,又等价于ax+by=1。
  当用扩展欧几里德算法,求出它的一组解x0和y0时,可得ax0+by0=1。
  那么只要在方程左边加上一个kab,再减去一个kab,合并同类项可得:
  a+b=1。
  x=x0+kb,y=y0-ka就是方程的通解,k可以为负数、0、或正数。
  这里我们只关心x的取值,于是接下来,只要求出等于x0+kb的最小正整数,就可以了。
  为什么给x0加上一个kb,而不是某个比b小的数与k的乘积?
  很简单,如果那么做,就找不到能使等式成立的y了……
  因为x0有可能为负数,所以要分两种情况讨论。
  当x0大于0时,显而易见,x0%b也大于0,所以最小的正整数x就是x0%b本身。
  而当x0≤0时,x0%b也必然≤0,因为|x0%b|必定小于b,所以只需要在x0%b的结果上,再加上一个b,就可以得到最小的正整数解了。
  推演到这里,结论就很明确了。
  江寒马上将代码稍加修改,再次一调试,这次就顺利通过了。
  啧,出题的人挺阴险的嘛。
  如果生搬硬套扩展欧氏算法,没准一不小心就会掉进坑里去……
  虽然这么一个小坑,应该也困不住太多人就是了。
  第一题搞定之后,江寒就开始思考下一道题。
  第二题:借教室。
  【问题描述】:……
  这道题和Day1的第三题差不多,都是那种表述啰嗦得要死,但只要看明白题意,就会觉得异常简单的题型。
  江寒直觉可以用线段树来弄。
  事实上,应该也是行得通的。
  但一般说来,线段树中的pushdown常数都特别巨大,很容易溢出。
  所以,如果没什么特别的优化手段,最多通过70%的数据校验点,也就差不多达到极限了。
  要想过掉100%的校验点,达到AllClear的境界,就必须使用二分答案法,再加上前缀和差分……
  正打算换个思路来破题,江寒忽然想起了什么,拿起草稿纸一阵推演。
  五分钟后,他长出了一口气,然后开始画流程、写伪代码。
  他没有改变算法,仍然使用了线段树,只不过在标准的算法中,稍微做了一点小改进。
  办法很简单,就是将线段树的标记固定化了,在区间完全重合的时候,只是打上修改标记,而不去pushdown标记。
  在查询的时候,顺便将每个位置标记上,要算的值都放在下一层递归里,这样就大大优化了线段树的pushdown常数。
  标记的删除非常方便,要把一个区间改回去,只需要把最外层的几个小区间标记置0就行。
  这么一改进,就能大大减少运算量,从而有很大的机会通过全部数据了。
  江寒写完增强线段树算法,又编写了一段测试代码,用各种极限值去测试。
  结果非常喜人,在100%的数据输入区间,都能轻松在1秒内得到答案。
  第二题就此搞定。
  时间到此才过去1个小时20分钟,还剩下两个多小时。
  那么,接下来就一鼓作气,搞定最后一题。
爱小说WWW.IXS.CC努力创造无弹窗阅读环境,大家喜欢就按 Ctrl+D 加下收藏吧,有你们的支持,让我们走得更远!
可以使用回车、←→快捷键阅读