n和p是9或10位数字。如果将它们限制为32位(unsigned long)值，则可以使用简单的(二进制)模数幂运算找到2^n mod p。unsigned long long u = 1, w = 2;
while (n != 0)
{
if ((n & 0x1) != 0)
u = (u * w) % p; /* (mul-rdx) */
if ((n >>= 1) != 0)
w = (w * w) % p; /* (sqr-rdx) */
}
r = (unsigned long) u;
(2^n - 1) mod p = r - 1 mod p ：
r = (r == 0) ? (p - 1) : (r - 1);
2^n mod p = 0，但实际上如果p > 2是质数，则不会发生这种情况，但我们可以考虑一般情况，那么(2^n - 1) mod p = -1 mod p。(mod p)在[0，p-1]中，因此我们添加了一些p的倍数，使其在此范围内。2^n mod p的结果将在[1，p-1]中，并且减去1将已经在此范围内。可能更好地表达为：if (r == 0)
r = p - 1; /* -1 mod p */
else
r = r - 1;
要进行模运算，你必须拥有2^n-1，否则你将进入不同的算法方向，虽然很有趣但是与此无关。因此我建议你使用大整数概念，这样会更容易...可以制定一个结构并在小值中实现大值，例如：
struct bigint{
int lowerbits;
int upperbits;
}
语句的分解也有解决方案，例如 2^n = (2^n-4 * 2^4 )-1%p，将它们分解并分别处理，那将是相当算法化的。
要计算 2^n - 1 mod p，您可以在从 n 中删除 (p-1) 的任何倍数后使用平方指数法（因为 a^{p-1} = 1 mod p）。伪代码如下：
n = n % (p - 1)
result = 1
pow = 2
while n {
if n % 2 {
result = (result * pow) % p
}
pow = (pow * pow) % p
n /= 2
}
result = (result + p - 1) % p
我在HackerRank上解决数学问题时，遇到了这里发布的答案，并且它已经适用于那里给出的所有测试用例。
如果将n和p限制为64位（无符号长）值，则以下是数学方法：
2^n - 1可以写成1*[ (2^n - 1)/(2 - 1) ]
仔细观察一下，这是GP的总和1 + 2 + 4 + .. + 2^(n-1)
我们知道(a+b)%m = ( (a%m) + (b%m) )%m
如果您对上述关系是否适用于加法感到困惑，您可以搜索一下或查看此链接：http://www.inf.ed.ac.uk/teaching/courses/dmmr/slides/13-14/Ch4.pdf
所以，现在我们可以将上述关系应用于我们的GP，你就能得到答案了！ 也就是说，(2^n - 1)%p等价于(1 + 2 + 4 + .. + 2^(n-1))%p，然后应用给定的关系。首先，关注2n mod p，因为最后总是可以减去1。
考虑二的幂次方。这是通过重复乘以二产生的一系列数字。
考虑模运算。如果将数字写成p进制，你只需要获取最后一位数字。高位数字可以被丢弃。
因此，在序列中的某些点上，你会得到一个两位数（p位上为1），你的任务实际上就是在发生这种情况时摆脱第一个数字（减去p）。
概念上停留在这里，暴力方法可能是这样的：
uint64_t exp2modp( uint64_t n, uint64_t p ) {
uint64_t ret = 1;
uint64_t limit = p / 2;
n %= p; // Apply Fermat's Little Theorem.
while ( n -- ) {
if ( ret >= limit ) {
ret *= 2;
ret -= p;
} else {
ret *= 2;
}
}
return ret;
}
不幸的是，对于大的n和p，这仍然需要很长时间，我想不到任何更好的数论方法。
如果您有一个可以计算(p-1)^2而不会溢出的乘法设施，则可以使用类似的算法，在每次平方操作后使用模数进行重复平方，并在每次乘法后再次使用模数取平方残差系列的乘积。
步骤1. x = 将1左移n次，然后减去1
步骤2. result = x和p的逻辑与操作