Переполнение силой
Если я вычисляю [x * (a ^ b)% mod + y% mod]% mod, если я просто использую (a ^ b)% mod, умножим ли это на x правильный ответ? Не лучше ли рассчитать (x * (a ^ b))% mod по шагам? Просто пытаюсь доказать себе, почему не включая х работает.
Что можно сделать?
Решение
Попробуйте этот код. Идея состоит в том, чтобы ввести новые функции для модульного сложения, умножения и возведения в степень:
#define MOD 1000000007
inline int modadd(int a, int b) {
return ((long long)a + b) % MOD;
}
inline int modmult(int a, int b) {
return ((long long) a * b) % MOD;
}
inline unsigned modexp(unsigned base, unsigned exp)
{
unsigned result = 1;
while (exp > 0) {
if (exp & 1) result = ((unsigned long long)result * base) % MOD;
base = ((unsigned long long)base * base) % MOD;
exp >>= 1;
}
return result;
}
int main(void)
{
unsigned A[3] = {1, 2, 3};
unsigned r[3];
unsigned i, n = 3;
r[0] = 0;
r[1] = modmult(2, A[0]);
for (i = 1; i < n; i++) {
r[i+1] = modadd(r[i], modmult(A[i], modexp(2, i)));
}
}
Другие решения
Других решений пока нет …