一个大数n，验证一个整数m是否是n的因子，时间复杂度该如何算

一个大数n，验证一个整数m是否是n的因子，时间复杂度该怎么算
在一个文档上看到：对一个大数n，其输入的规模是log n，因为n可以被log n个输入表示。。

接下来，要验证一个整数m是否是n的因子，时间复杂度该怎么算？

诚心求教！
[解决办法]
大数乘除法的时间复杂度n都是按位算的，当然进制可能是10^x或者2^y。
不管是FFT还是FNT，乘法都是O(n*log(n))。优化过的牛顿迭代法实现的除法也是O(n*log(n))，不过常数项是乘法的2倍。
[解决办法]

引用:

我有个疑问：验证一个大数n是否是素数，为什么是np问题？

用p问题的定义也很容易解释的通啊，既然是np问题，任一个数都可以在多项式时间验证是否是n的因子，那么哪怕用最暴力的办法把每个小于n的数都验证一遍。无非是把刚才的多项式时间再乘以一个n，不还是多项式时间吗？既然多项式时间里找出了解，不就是p问题吗？

是不是我什么地方理解错了？求赐教！

再次重复：大数问题的时间复杂度是按位算的。比如对于10进制而言，10^n 全部扫一遍就是O(10^n)。

查看更多 下一篇