c - Optimizing my algorithm for multiplication modulo -

i have problem internet have array of n integers , have perform segment multiplication t times given left(l) , right segment(r) of array , return answer modulo given modulus(m).

constraints

n,t<=100000

1<=l<=r<=n

m<=10^9

and integers <=100

ex-

input

5(n) 2 5 8 9 4 4(t) 1 2 3 2 3 4 1 1 1 1 5 100000

output

1 0 0 2880

so have made solution problem little slow need tips optimize program.

#include "stdio.h"  int main(void) {         int t;         scanf("%d",&t);          int array[t+1];       (int = 1; <=t; i++)     {         scanf("%d",&array[i]);     }      int n;     scanf("%d",&n);       (int = 0; <n ; i++)     {          long long a,b,c;         scanf("%lld%lld%lld",&a,&b,&c);         long long product = 1;         if (c==1)         {             product = 0;          }         else         {              (int j = a; j <=b ; j++)             {                  product *= array[j];                  if (product>=10000000000000000)                 {                     product%=c;                 }             }          }          product%=c;           printf("%lld\n",product );      }      return 0; } 

hints

you compute array a_p[i] each prime p less 100 notes how many times p divides i^th entry of array.

then can compute secondary array b_p[j] cumulative sum of a_p[i] , including j. (this can done in o(n) recursion b_p[i]=b_p[i-1]+a_p[i].)

this secondary array allow compute total power of each prime in range. example, if wanted know how many times prime 5 appeared in array entries 10 100 can compute b_5[100]-b_5[10-1].

so each query can compute final answer raising each prime corresponding power , multiplying results modulo m. note there technique called exponentiation squaring makes calculation efficient.

if 0 possible integer, add 0 list of primes considered in calculation.

for interest

note approach of using cumulative sum quite useful in many situations. example, viola-jones method face recognition uses version of technique in 2 dimensions in order able compute 2d filters efficiently.