Может ли n% = m возвращать отрицательное значение для очень больших неотрицательных n и m?

Question

Этот вопрос относится к оператору modulo %. Мы знаем, что вообще a % b возвращает остаток, когда a делится на b, а остаток больше или равен нулю и строго меньше b. Но выполняется ли это выше, когда a и b имеют величину 10^9?

я, кажется, получаю отрицательный выход для следующего кода для ввода:

74 41 28 

Однако изменение окончательного вывода о делает работу, и результат становится правильным!

#include<iostream> 
    using namespace std; 

    #define m 1000000007 

    int main(){ 
     int n,k,d; 
     cin>>n>>k>>d; 
     if(d>n) 
     cout<<0<<endl; 
     else 
     { 
      long long *dp1 = new long long[n+1], *dp2 = new long long[n+1]; 

      //build dp1: 
      dp1[0] = 1; 
      dp1[1] = 1; 

      for(int r=2;r<=n;r++) 
      { 
       dp1[r] = (2 * dp1[r-1]) % m; 
       if(r>=k+1) dp1[r] -= dp1[r-k-1]; 
       dp1[r] %= m; 
      } 

      //build dp2: 
      for(int r=0;r<d;r++) dp2[r] = 0; 
      dp2[d] = 1; 

      for(int r = d+1;r<=n;r++) 
      { 
      dp2[r] = ((2*dp2[r-1]) - dp2[r-d] + dp1[r-d]) % m; 
      if(r>=k+1) dp2[r] -= dp1[r-k-1]; 
      dp2[r] %= m; 
      } 

      cout<<dp2[n]<<endl; 
     } 
    } 

изменения окончательного вывода заявление:

 if(dp2[n]<0) cout<<dp2[n]+m<<endl; 
     else cout<<dp2[n]<<endl; 

делает работу, но почему это требовалось?

Кстати, код на самом деле мое решение this question

Answer 1

Это ограничение накладывается диапазоном int.

int может содержать только значения между -2147483648 к .

Рассмотрите возможность использования long long для ваших переменных m, n, k, d & r. Если возможно, используйте unsigned long long, если ваши расчеты никогда не должны иметь отрицательного значения.

long long может содержать значения от -9,223,372,036,854,775,808 к 9,223,372,036,854,775,807

в то время как unsigned long long может содержать значения от 0 до 18,446,744,073,709,551,615. (2^64)

Диапазон значений положительных значений примерно в два раза меньше по сравнению с неподписанными типами, что связано с тем, что для знака используется самый старший бит; Когда вы пытаетесь назначить положительное значение, превышающее диапазон, заданный указанным типом данных, старший бит увеличивается и интерпретируется как отрицательное значение.

Answer 2

Математически нет ничего особенного в больших числах, но компьютеры имеют ограниченную ширину, чтобы записывать числа, поэтому, когда вещи становятся слишком большими, вы получаете ошибки «переполнения». Обычная аналогия - это счетчик миль, пройденный на приборной панели автомобиля - в конечном итоге он будет отображаться как все 9 и катится до 0. Из-за того, что обрабатываются отрицательные числа, стандартные знаковые целые числа не округляются до нуля, а к очень большой отрицательный число.

Вам нужно переключиться на более крупные типы переменных, чтобы они быстрее переходили - «long int» или «long long int» вместо «int», удваивая диапазон с каждым дополнительным битом ширины. Вы также можете использовать unsigned типы для дальнейшего удвоения, так как для негативов не используется диапазон.

Answer 3

Ну, нет, modulo с положительными операндами не дает отрицательных результатов.

Однако .....

Тип int гарантируется только стандартами C для поддержки значений в диапазоне от -32767 до 32767, что означает, что ваш макрос m не обязательно расширяется до литерала типа int. Он будет вписываться в длинный, хотя (который, как гарантируется, имеет достаточно большой диапазон).

Если это происходит (например, компилятор с 16-разрядным типом типа и 32-разрядным длинным типом), результаты ваших операций с модулем будут вычисляться как долго и могут иметь значения, превышающие значения, которые может представлять int , Преобразование этого значения в int (как требуется для операторов типа dp1 [r]% = m, поскольку dp1 является указателем на int) дает неопределенное поведение.