为什么在数字大于 48 位的情况下函数会失败?
Why the function is failing in case of numbers greater than 48 digits?
我正在寻找
(a^b) % mod
其中 b 和 mod 最大为 10^9,而 l 可以非常大我已经成功测试了最多 48 位数字
使用这个关系
(a^b) % mod = (a%mod)^b % mod
#define ll long long int
ll powerLL(ll x, ll n,ll MOD)
{
ll result = 1;
while (n) {
if (n & 1)
result = result * x % MOD;
n = n / 2;
x = x * x % MOD;
}
return result;
}
ll powerStrings(string sa, string sb,ll MOD)
{
ll a = 0, b = 0;
for (size_t i = 0; i < sa.length(); i++)
a = (a * 10 + (sa[i] - '0')) % MOD;
for (size_t i = 0; i < sb.length(); i++)
b = (b * 10 + (sb[i] - '0')) % (MOD - 1);
return powerLL(a, b,MOD);
}
powerStrings("5109109785634228366587086207094636370893763284000","362323789",354252525) returns 208624800 但它应该 return [=[=2435=]30=] 26=]。在这种情况下 a 是 49 位
powerStrings("300510498717329829809207642824818434714870652000","362323489",354255221) returns 282740484 ,这是正确的。在这种情况下 a 是 48 位
代码有问题还是我必须使用其他方法来做同样的事情??
它不起作用,因为它在数学上不正确。
一般来说,我们有 pow(a, n, m) = pow(a, n % λ(m), m)
(a
与 m
互质),其中 λ
是 Carmichael function. As a special case, when m
is a prime number, then λ(m) = m - 1
. That situation is also covered by Fermat's little theorem。那只是一个特例,并不总是有效。
λ(354252525) = 2146980
,如果我hack that in那么正确的结果就出来了。 (虽然基数实际上并不是模数的互质)
一般来说,您需要为模数计算 Carmichael 函数,这很重要,但对于小模数是可行的。
我正在寻找
(a^b) % mod
其中 b 和 mod 最大为 10^9,而 l 可以非常大我已经成功测试了最多 48 位数字 使用这个关系
(a^b) % mod = (a%mod)^b % mod
#define ll long long int
ll powerLL(ll x, ll n,ll MOD)
{
ll result = 1;
while (n) {
if (n & 1)
result = result * x % MOD;
n = n / 2;
x = x * x % MOD;
}
return result;
}
ll powerStrings(string sa, string sb,ll MOD)
{
ll a = 0, b = 0;
for (size_t i = 0; i < sa.length(); i++)
a = (a * 10 + (sa[i] - '0')) % MOD;
for (size_t i = 0; i < sb.length(); i++)
b = (b * 10 + (sb[i] - '0')) % (MOD - 1);
return powerLL(a, b,MOD);
}
powerStrings("5109109785634228366587086207094636370893763284000","362323789",354252525) returns 208624800 但它应该 return [=[=2435=]30=] 26=]。在这种情况下 a 是 49 位
powerStrings("300510498717329829809207642824818434714870652000","362323489",354255221) returns 282740484 ,这是正确的。在这种情况下 a 是 48 位
代码有问题还是我必须使用其他方法来做同样的事情??
它不起作用,因为它在数学上不正确。
一般来说,我们有 pow(a, n, m) = pow(a, n % λ(m), m)
(a
与 m
互质),其中 λ
是 Carmichael function. As a special case, when m
is a prime number, then λ(m) = m - 1
. That situation is also covered by Fermat's little theorem。那只是一个特例,并不总是有效。
λ(354252525) = 2146980
,如果我hack that in那么正确的结果就出来了。 (虽然基数实际上并不是模数的互质)
一般来说,您需要为模数计算 Carmichael 函数,这很重要,但对于小模数是可行的。