这个脚本可以使用模幂运算获得更好的性能吗?
Can this script have better performance using modular exponentiation?
def f(a, b, c):
return ((a ** b)-1) // c % b
这个脚本可以在某些方面更快吗? (我一直在寻找模幂的东西):
pow(a, b, c) == a ** b % c
但是上面的脚本似乎不能像那样改进。有谁知道加速上述脚本的方法?提前致谢。
编辑:
第二个脚本与第一个完全不同,它只是为了展示我的想法。
编辑:
我没有输入确切的方程式,因为我想要一个通用的案例解决方案,
具体是当 a = 4 和 c = 3 时。这样会更容易吗?
编辑:
我收到要求说清楚我是想先减法还是先求幂,我想先求幂,我通过加括号明确了。
请注意,a**b//c%d == a**b%(c*d)//c%d
适用于任何正整数。这是真的,因为存在一个正整数 k
使得 a**b == k*c*d + a**b%(c*d)
成立并且右侧的运算结果 //c%d
不受任何 k
的影响。
根据这个事实,a**b//c%d
可以用命令
计算出来
pow(a,b,c*d)//c%d
def f(a, b, c):
return ((a ** b)-1) // c % b
这个脚本可以在某些方面更快吗? (我一直在寻找模幂的东西):
pow(a, b, c) == a ** b % c
但是上面的脚本似乎不能像那样改进。有谁知道加速上述脚本的方法?提前致谢。
编辑:
第二个脚本与第一个完全不同,它只是为了展示我的想法。
编辑:
我没有输入确切的方程式,因为我想要一个通用的案例解决方案, 具体是当 a = 4 和 c = 3 时。这样会更容易吗?
编辑:
我收到要求说清楚我是想先减法还是先求幂,我想先求幂,我通过加括号明确了。
请注意,a**b//c%d == a**b%(c*d)//c%d
适用于任何正整数。这是真的,因为存在一个正整数 k
使得 a**b == k*c*d + a**b%(c*d)
成立并且右侧的运算结果 //c%d
不受任何 k
的影响。
根据这个事实,a**b//c%d
可以用命令
pow(a,b,c*d)//c%d