如何在更短的时间内有效地完成这类问题?我试图用Python来解决这个问题,但它花费了很多时间。我一直在想,也许^
意味着xor不是权力,但根据他们这是权力。这是编码竞赛的一个问题。计算i^2453467 mod 2453468的总和为1 <= i <= 999999(^意味着功率)
回答
https://en.wikipedia.org/wiki/Modular_exponentiation
聚焦计算的存储器高效的方法。应该是相当简单的实施。
我认为'从右到左的二进制方法似乎更好 – throwit
在一般的情况下,是的,你应该更好地利用模幂,这的确是相当简单,如@ F.Ju。然而,用一点数学,你可以用笔和纸完全计算总和。
关键要注意的是指数(2453467
)非常接近模数(2453468
),这就需要一个更简单的表示x^2453467 mod 2453468
。事实上,如果2453468是素数,则根据Fermat's little theorem,x^2453467 mod 2453468
总是1
。
虽然这不是首要的,但它有一个非常简单的表示2*2*613367
。所以我们可以记住Euler's theorem,发现phi(2453468)
等于1226732
,所以2453467=2*phi(2453468)+3
。因此,对于与2453468
相对较好的每个x
,我们有x^1226732=1
,并且,因为2453467
是1226732*2+3
,所以我们有x^2453467 mod 2453468=x^3 mod 2453468
。
让我们再考虑一些不是2453468
的质数。在超出范围(1至999999)中,有三种数字与2453468
不相对。一个是613367
,并且相对容易证明613367^(2k+1) mod 2453468=613367
为每个k
。
另一种是可被4整除的数字。对于数字x=4k
,我们需要找到(4k)^2453467 mod (4*613367)
。它相当于4*(4^2453466*k^2453467 mod 613367) mod (4*613367)
,稍微有一点费马定理,这减少到(4k)^3 mod (4*613367)
。
最后一种是可以被2整除的数字,但不是4,它们的处理方式与前一种相同。
其结果是,我们有
每
x
从1到999999,x^2453467 mod 2453468 = x^3 mod 2453468
因此,我们需要从计算
sum(x^3) mod 2453468
为x
1至999999。
但模数运算下的总和众所周知只是(n(n+1)/2)^2
,n
是999999
。因此,我们的答案是499999500000^2 mod 2453468
,其计算结果为2385752
。
1好吧,差不多。我用Python来做简单的算术。
- 1. 什么<?意味着
- 2. makefile中的$ <和$ @意味着什么?
- 3. << - 是否意味着红宝石?
- 4. (1 << 32)和(1 << i)之间的区别其中i == 32
- 5. 计算意味着处理NaN意味着
- 6. operator <<:std :: cout << i <<(i << 1);
- 7. 汇总功能组,计数和意味着
- 8. <<<在shell脚本中意味着什么?
- 9. 这是什么用途的<<意味着在Python
- 10. Modernizr.load(Yepnope)意味着在<head>
- 11. 是什么阵<T?>意味着
- 12. 计算N个功率的总和
- 13. <xsd:include schemaLocation =“some.xsd”/>意味着什么
- 14. <?=这在C++中意味着什么?
- 15. 什么呢<built-in>,<命令行>意味着
- 16. 通过Proc的概率计算意味着T检验
- 17. 计算意味着在分组行
- 18. 什么是:newImg(newImg <1)= 0,是否意味着?
- 19. XML标签意味着
- 20. 计算矩阵列意味着
- 21. 计算意味着numpy的阵列对
- 22. 计算意味着在一个列表
- 23. 使用mpz_powm计算功率mod
- 24. “NSBinarySearchingFirstEqual =(1UL << 8)”在枚举定义中意味着什么?
- 25. <<在Swift语言中意味着什么?
- 26. 什么“<<!”在Linux shell中意味着什么?
- 27. “云计算”究竟意味着什么?
- 28. 什么perl的-I意味着
- 29. 意味着功能产生
- 30. 这个C++代码是什么意思是“sol <?= f((1 << n)-1,i,0)+ abs(P [i])* price;”
显示您的代码。 –
常数(即2453467和2453468)是否固定? – Petr