• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2115 – C Looooops

    ACM-POJ EXP 232阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    对于C的for(i=A ; i!=B ;i +=C)循环语句,问在k位存储系统中循环几次才会结束。

    若在有限次内结束,则输出循环次数。

    否则输出死循环。

    解题思路

    题意不难理解,只是利用了** k位存储系统** 的数据特性进行循环。

    例如int型是16位的,那么int能保存2^16个数据,即最大数为65535(本题默认为无符号),

    当循环使得i超过65535时,则i会返回0重新开始计数

    如i=65534,当i+=3时,i=1

    其实就是 i=(65534+3)%(2^16)=1

    有了这些思想,设对于某组数据要循环x次结束,那么本题就很容易得到方程:

    x=[(B-A+2^k)%2^k] /C

    即 Cx=(B-A)(mod 2^k) 此方程为 模线性方程,本题就是求X的值。


    下面将结合《算法导论》第2版进行简述,因此先把上面的方程变形,统一符号。

    令a=C

    b=B-A

    n=2^k

    那么原模线性方程变形为:

    ax=b (mod n)

    该方程有解的充要条件为 gcd(a,n) | b ,即 b% gcd(a,n)==0

    令d=gcd(a,n)

    有该方程的 最小整数解为 x = e (mod n/d)

    其中e = [x0 mod(n/d) + n/d] mod (n/d) ,x0为方程的最小解

    那么原题就是要计算b% gcd(a,n)是否为0,若为0则计算最小整数解,否则输出FOREVER

    当有解时,关键在于计算最大公约数 d=gcd(a,n) 与 最小解x0

    参考《算法导论》,引入欧几里得扩展方程 d=ax+by

    通过EXTENDED_EUCLID算法(P571)求得d、x、y值,其中返回的x就是最小解x0,求d的原理是辗转相除法(欧几里德算法

    再利用MODULAR-LINEAR-EQUATION-SOLVER算法(P564)通过x0计算x值。注意x0可能为负,因此要先 + n/d 再模n/d。

    以上方法的推导过程大家自己看《算法导论》。。。这里不证明,只直接使用。


    注意

    计算n=2^k时,用位运算是最快的,1<<k (1左移k位)就是2^k

    但是使用long long的同学要注意格式, 1LL<<k

    使用__int64的同学要强制类型转换 (__int64)1<<k

    不然会WA

    Source修正

    CTU Open 2004

    测试数据

    本文第二页附带测试数据

    测试数据下载


    转载请注明:EXP 技术分享博客 » POJ2115 – C Looooops

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址