0

so I have an assignment to make a power program. but because of its big number, its must be modulo by 10^9 + 7. The program was executed too long. What should I do to reduce executing the program?

Sorry for my bad english.

#include <stdio.h>

int main () {
    
    int t;
    int i;
    long long int temp;

    scanf("%d", &t);
    
    for (i = 1; i <= t; i++) {
        
        long long int a, n;
        scanf("%lld %lld", &a, &n);
        
        long long int total = 1;
        long long int mod = 1000000007;
        
        for (temp = 1; temp <= n; temp++) {
            
            total = ((total % mod) * (a % mod)) % mod; 
        
        }
            
        printf("Case #%d: %lld\n", i, total);
    }

}
Weather Vane
  • 33,872
  • 7
  • 36
  • 56
chewei darmajaya
  • 1
  • https://en.wikipedia.org/wiki/Exponentiation_by_squaring – Marco Bonelli Oct 24 '22 at 19:04
  • Your algorithm will take *a lot* of time when `n` is (2^63 - 1). Use the exponentiation algorithm [The most efficient way to implement an integer based power function pow(int, int)](https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int). The modulus is 32-bit, so use 64-bit variables and apply the modulus after each multiplication. – Weather Vane Oct 24 '22 at 19:13
  • ...and *initially* to the base value `a` once. – Weather Vane Oct 24 '22 at 19:46
  • Does this answer your question? [The most efficient way to implement an integer based power function pow(int, int)](https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int) – JGurtz Oct 26 '22 at 07:28

0 Answers0