CODEWITHSUNDEEP
math
user1301541
user1301541

Reputation: 149

Subtraction of very large numbers with modulus

I need to subtract two very large integers along with modulus of 1000000007

x and y are integers 1 <= x,y <= 1000

long long s[x+1];
long long c[x+1];

for(int i=1;i<=x;i++)
  c[i] = power(y,i)%mod;

s[1]=1;
for(int i=2;i<=x;i++){
    sum=0;
    for(int j=1;j<i;j++){
        sum = (sum + (s[j]*c[i-j]%mod))%mod;
    }
    s[i] = (c[i] - sum)%mod; // <----------- s[i] is -ve 
}

The issue is when c[i]%mod is less than Sum%mod

Eg: When c[i] is greater than Sum.
But c[i]%mod is less than Sum%mod
437001927 - 952742480

Upvotes: 1

Views: 511

Answers (2)

starblue
starblue

Reputation: 56782

I would use

s[i] = (c[i] - sum + mod) % mod;

in this case. sum is computed modulo mod, so it can't be greater than mod.

Upvotes: 1

Alex Chamberlain
Alex Chamberlain

Reputation: 4207

You could just add an if statement.

if(s[i]<0)
  s[i] += mod

Upvotes: 1

Related Questions