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

    ACM-POJ EXP 179阅读 0评论

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


    大致题意

    给定一个大数K,K是两个大素数的乘积的值。

    再给定一个int内的数L

    问这两个大素数中最小的一个是否小于L,如果小于则输出这个素数。

    解题思路

    首先对题目的插图表示无语。。。

    高精度求模+同余模定理

    解题步骤:

    1、 Char格式读入K。把K转成千进制Kt,同时变为int型。

    把数字往大进制转换能够加快运算效率。若用十进制则耗费很多时间,会TLE。

    千进制的性质与十进制相似。

    例如,把K=1234567890转成千进制,就变成了:Kt=[ 1][234][567][890]。

    为了方便处理,我的程序是按“局部有序,全局倒序”模式存放Kt

    即Kt=[890][567][234][1 ] (一个中括号代表一个数组元素)

    2、 素数打表,把10^6内的素数全部预打表,在求模时则枚举到小于L为止。

    注意打表不能只打到100W,要保证素数表中最大的素数必须大于10^6,否则当L=100W且K为GOOD时,会因为数组越界而RE,这是因为越界后prime都是负无穷的数,枚举的while(prime[pMin]<L)循环会陷入死循环

    3、 高精度求模

    主要利用Kt数组和同余模定理。

    例如要验证123是否被3整除,只需求模124%3

    但当123是一个大数时,就不能直接求,只能通过同余模定理对大数“分块”间接求模

    具体做法是:

    先求1%3 = 1

    再求(1*10+2)%3 = 0

    再求 (0*10+4)% 3 = 1

    那么就间接得到124%3=1,这是显然正确的

    而且不难发现, (1*10+2)*10+4 = 124

    这是在10进制下的做法,千进制也同理,*10改为*1000就可以了

    Source修正

    Nordic 2005

    测试数据

    本文第二页附带测试数据

    测试数据下载

    转载请注明:EXP 技术分享博客 » POJ2635 – The Embarrassed Cryptographer

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

    表情

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

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