纯个人感悟,解释错误的地方希望可以指出来,谢谢!这里是ACM的题目感悟,可惜不记得题目了,晕!估计做ACM的都见过容器倒水问题和捕捉神兽问题,以下就是这两个问题分析后的感悟:
两个杯倒水问题中,能否到处满意的水可以这样判断:
抓神兽的问题中,将直线转化为2倍直线长度的圆考虑,也就是求神兽每次跳跃的n在长度为m的圆中能否跳到距标记起点position长度的地方(求余),现在的问题其实转化为求m与n的最大公约数问题(因为:设m=a*y1,n=a*y2(这里a为最大公约数,且y1与y2互质,即y1,y2的线性差可以构造出任意的整数),若是能到达position,则(t*n)%m=position(t,x为未知的整数)即:t*a*y2=a*y1*x+position(x为未知的整数),即:t*y2=y1*x+position/a)若要求t有解则a一定能被position整除,即:position要是m,n的最大公约数的倍数才有解。
类似的可以推广到两容器倒水问题(将一个容器的水不停的往另一个容器倒的类似捕神兽的圆圈问题),也可以用所求水的容积是否为两容器的最大公约数的倍数(当然,所求体积不能大于最大容器的容量)。