Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

不一定就是lg(b)了。举个例子（虽然是特殊情况）当gcd(a,m)=1时，a^b mod m = a^(b%(phi(m))) mod m。这样只需要lg(m)的复杂度

Posted by RoBa at 2007-10-07 21:05:11 and last updated at 2007-10-08 15:35:34
In Reply To:Re:可以的,复杂度和输入的运符个数有关,和怎么组合无关 Posted by:xwbsw at 2007-10-07 21:01:16

> 求 a^b 本身复杂度就是lg(b)的,前面又要乘大数运算的系数,怎么能说完全无关?

Followed by:

我们考虑的都是最普通的情况,倒是没想这么复杂,不过以后一定会多加注意的,多谢诸位大牛的建议. (0) xwbsw 2007-10-07 21:10:01
- 离正赛还有老长时间，文字和数据都多加小心吧，吉大之前怎么说都应该有无数经验了，表现出来就好 (0) frkstyc 2007-10-07 21:12:37
  - 恩，今天文字上出了很多很多很多错。 (61) sharang 2007-10-07 21:38:06
我觉得数据不应该考虑特殊情况，那样就有点搜索题的意思了。。。D的数据没有BT的，除了阶乘的小陷阱。其实说白了，这就是个大模拟 (0) sharang 2007-10-07 21:39:54
- roba说的东西不是不能推广到一般情形的…… (0) frkstyc 2007-10-07 21:47:21
  - 我们就是推广的时候出错了... (0) RoBa 2007-10-07 21:49:41
    - 推广起来很折腾，要因数分解什么的……但我觉得不是不能做…… (0) frkstyc 2007-10-07 21:50:48
      - 噢~原来如此，受教了呵呵。确实高手一般做题都是先确定不TLE再写代码~ (0) sharang 2007-10-07 21:59:37
      - 这题很特殊,模数都只含2和5,如果模一个一般数恐怕就不好做了 (0) wanglei 2007-10-07 22:03:56
        啊，我想出题者选择10^40可能是比较好取模，纯属猜测，呵呵 (0) sharang 2007-10-07 22:07:24
        是买的题？ (0) forgotten 2007-10-07 22:27:52
        ms不是吧…… (0) frkstyc 2007-10-07 22:29:33
        那真是买了一套牛强的题阿！ (0) Volcanon 2007-10-07 22:33:20
        这个题不用买吧。。。你出多少我卖给你。。。 (0) sharang 2007-10-07 22:37:48
        多谢你的好意了。我们学校向来都是超自信的，自己出题 (0) Volcanon 2007-10-07 23:11:06
        -_-||| (0) xwbsw 2007-10-07 22:36:58

Post your reply here:

Home Page Go Back To top