0

I want to sum a GP with common diff = -1/3, first term = 3^(n-1) till last term = +3/-3(depends on n). I know I can use the pow function but i want the answer to be mod 10^9+7 as n can be very large (like-1000000). My main problem is that when I input n greater than approx 25 I start getting negative output (for ex. when n=30 --> output = -3007262). I also checked here and tried the code here but the answer again started to become negative for larger numbers. Can anyone tell me a good faster and precise way to do this? my code (bad, ik): 

#include <iostream>
using namespace std ;
long long ipow(int p , int k ){
    long long ans = 1;
    for(int i = k ; i > 0;--i ){
        ans *= p;
        ans %= 1000000007;
    }
    return ans;
}
int main(){
    long long ans =0;
    int n;
    cin >> n;
    if(n%2 != 0){
        for(int i = n-1; i >0 ; i-=2){
            ans += ipow(3,i);
            ans -= ipow(3,i-1); 
        } 
        cout<< ans%1000000007<<"\n" ; 
    }
    else{
        for(int i = n-1; i >0 ; i-=2){
            ans += ipow(3,i);
            ans -= ipow(3,i-1); 
        }
        cout<< (ans+1)%1000000007<<"\n" ;  
    }
    return 0 ;
}

ps : You can see above I also didn't use the direct formula for a sum of a GP because the common diff is -1/3 but I want the answer to be int and when converting the answer from double (output is in double when pow function is used with input as -1/3) to int does not give me the precise int in many cases.

Dhrxv
  • 33
  • 5
  • If `int` is 32 bit which is the case on most modern PCs your multiplications can overflow since the maximum possible intermediate value (1000000006^2) is greater than 2^31-1. You need to do your multiplications using a bigger type. Also, look into [binary exponentiation](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) for a faster way to compute modular exponents. – eesiraed Jun 10 '20 at 05:21
  • The `%` operator can return negative values if the first operand is negative, so you need to be careful with your subtractions. – eesiraed Jun 10 '20 at 05:23
  • @BessieTheCow in my ipow function I used the long long data type for ans and also for the return type of the function but the answer is still negative and also I don't think long long will overflow as I am also taking mod 10^9+7 at the end of each loop – Dhrxv Jun 10 '20 at 05:54
  • And also there is going to be no problem with the subtraction as in each loop I am first adding 3^i and then subtracting 3^(i-1) which is clearly always positive – Dhrxv Jun 10 '20 at 05:56
  • 1
    @Dhrxv It's not necessarily positive – remember that those are `% 1000000007` and will "wrap around" as `i` grows. – molbdnilo Jun 10 '20 at 06:24
  • You need to maintain the modulus on `ans`, and not just apply it at the end. – molbdnilo Jun 10 '20 at 06:48
  • Thanks, I got it. I factored the 3^i from each pair and made them into a single positive term and added them all together. – Dhrxv Jun 10 '20 at 11:43

0 Answers0