Right! Right!
A(i) ≤ 100 was a hint for many (including me). But for me, the idea of prime numbers didn’t click before there were a few TLEs.
@sandeepandey Thank you for sharing!
@tijoforyou same story here. Apart from the fact that A(i) ≤ 100 was a hint i figured out at starting 
1 Like
I dont think this question qualifies as an easy one. It requires segment trees and modular exponentiation. Please consider moving it to medium. It took me 3 hours to get to the Algorithm. And only around 900 could solve it over the ten days.
i’d got AC and my power function was recursive too
Segmented Trees ? Why do you need that in this ?
using namespace std;
unsigned long long int pr(int a,int b,unsigned long long int m){
if(b == 0)return 1;
unsigned long long int ans = pr(a,b/2,m)%m;
if(b%2){
return (((a*ans)%m)*ans)%m;
}else{
return (ans*ans)%m;
}
}
int ans[100001][26];
int main()
{
int p[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
unsigned long long mod,aa;
int l = 25;
int arr[101][25] = {{0}};
for(int m = 2;m < 101;m++){
int awe = m;
for(int j = 0; j < l && awe > 1; j++) {
if(awe%p[j] == 0) {
while(awe%p[j] == 0) {
arr[m][j]++;
awe /= p[j];
}
}
}
}
int n;
cin >> n;
int in[n];
for(int i = 0;i < n;i++) {
scanf("%d",&in[i]);
}
for (int i = 0; i < 25; i++ ) {
ans[0][i] = arr[in[0]][i];
}
for(int i = 1;i < n;i++){
for(int j = 0;j < 25;j++){
ans[i][j] = ans[i-1][j] + arr[in[i]][j];
}
}
int final[26];
int k;
cin >> k;
while(k--){
int l,r;
scanf("%d%d%llu",&l,&r,&mod);
aa = 1%mod;
for(int i = 0;i < 25;i++){
if (l > 1)final[i] = ans[r-1][i] - ans[l-1][i] + arr[in[l-1]][i];
else final[i] = ans[r-1][i];
}
for(int i = 0;i < 25;i++){
if(final[i]){
aa = (aa*pr(p[i],final[i],mod));
if(aa >= mod)aa = aa%mod;
}
}
cout<< aa<<endl;
}
return 0;
}’
why i got TLE…can any one help me please…
Using Segment tree was my second approach as storing product of numbers in a product array table was my first approach but I was getting SIGFPE and then latter on WA on both the approaches.
What I was thinking is the highest value of mod is 10^9 and during calculation of product or formation of segment tree, i was taking mod of 10^9 + 7 in order to maintain in the size in int.
After then I thought perhaps this is not good idea so I implemented big integers in c++, this was my first handshake with big integers in c++, thanks to the problem I learned how to use big integers but still problems was not solved and got TLE’s.
Interesting. I used prime numbers in the first go and didn’t even notice that storing freqs of 1-100 could have been an alternative approach. To answer your question, I started solving the problem by looking at the segment products. I noticed that they’ll consists of only primes from 1 to 100 and that’s how I came up with the idea of storing prime frequencies. Thanks for this alternative view!
1 Like
I changed your recursive pr function to iterative one and viola!!! It worked…
http://www.codechef.com/viewsolution/2528330
I had this same prob. and I don’t know why recursive is failing in our case…as akrai48 has implemented it recursive…I think we have been doing things that aren’t optimized…Would be grateful if someone throw a light on it…
so was mine !
there so much bilions in result such that owerflow in even long double : result = k * 1e9 + x ; result <= 1e200,000 so , k <= ~1e20000
But when using log10, the max sum is 10.000 * 2 
this is giving TLE
anyone plz help
this is giving TLE
anyone plz help
can sm1 plss check why m i getting WA for my code…
http://www.codechef.com/viewsolution/2529589
i m getting all right answers for as many test cases as i could think of…am i missing sm exceptional case??
If you’re doing a naive D&C, query complexity would be Omega(n).
Your recurrence would be T(n) = 2 * T(n / 2) + Omega(1).
T(n) = Omega(n)
In your program, the line res=(res*power(i,tmp[i],m)); can give an overflow. It should have been res=(res*power(i,tmp[i],m))%m; to avoid overflows.