Может ли n% = m когда-либо возвращать отрицательное значение для очень больших неотрицательных n и m?
Этот вопрос касается оператора по модулю %, Мы знаем в общем 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;
работает, но зачем это было нужно?
Кстати, код на самом деле мое решение этот вопрос
Решение
Это предел, налагаемый диапазоном int,
int может содержать значения только между -2147483648 в 2147483647.
Рассмотреть возможность использования long long для вашего м, н, к, д & г переменных. Если возможно использовать 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)
Диапазон положительных значений примерно в два раза в знаковых типах по сравнению с неподписанными типами из-за того, что самый старший бит используется для знака; Когда вы пытаетесь присвоить положительное значение, превышающее диапазон, заданный указанным типом данных, самый старший бит повышается, и он интерпретируется как отрицательное значение.
Другие решения
Ну, нет, по модулю с положительными операндами не дает отрицательных результатов.
Тем не мение …..
Тип int гарантируется только стандартами C для поддержки значений в диапазоне от -32767 до 32767, что означает, что ваш макрос m не обязательно расширяется до литерала типа int. Это будет соответствовать длинному, хотя (который гарантированно имеет достаточно большой диапазон).
Если это происходит (например, компилятор, имеющий 16-битный тип int и 32-битный тип long), результаты ваших операций по модулю будут вычисляться как long и могут иметь значения, которые превышают то, что может представлять int. Преобразование этого значения в int (что потребуется для операторов типа dp1 [r]% = m, поскольку dp1 — указатель на int) дает неопределенное поведение.
С математической точки зрения в больших числах нет ничего особенного, но компьютеры имеют ограниченную ширину для записи чисел, поэтому, когда все становится слишком большим, вы получаете ошибки «переполнения». Типичная аналогия — счетчик миль, пройденных на приборной панели автомобиля — в конечном итоге он будет отображаться как все 9 и округляться до 0. Из-за способа обработки отрицательных чисел стандартные целые числа со знаком не округляются до нуля, а до очень большое отрицательное число.
Вам нужно переключиться на более крупные типы переменных, чтобы они переполнялись менее быстро — «long int» или «long long int» вместо просто «int», диапазон удваивался с каждым дополнительным битом ширины. Вы также можете использовать беззнаковые типы для дальнейшего удвоения, поскольку для негативов диапазон не используется.