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

• 这样当然不行了,要从最外层把运算符一层层剥掉,由一个求模运算转移到另一个 (0) wanglei 2007-10-07 21:03:26
• 不一定就是lg(b)了。举个例子（虽然是特殊情况）当gcd(a,m)=1时，a^b mod m = a^(b%(phi(m))) mod m。这样只需要lg(m)的复杂度 (46) RoBa 2007-10-07 21:05:11
  • 我们考虑的都是最普通的情况,倒是没想这么复杂,不过以后一定会多加注意的,多谢诸位大牛的建议. (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