Is the setter’s solution not up? I am getting a “Page Not Found”.
2 Likes
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.
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…
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??
What’s wrong with the following DP algo? (Not totally correct just the idea)
long long inputArray[n];
long long dp[n];
dp[0]=inputArray[0];
for(int i=1;i<n;i++)dp[i]=dp[i-1]*inputArray[i];
for(int i=0;i<queries;i++)
{
if(l==0)cout<<dp[r]<<endl;
else cout<<dp[r]/dp[l-1]<<endl;
}
Why is comlplexity of prime factorizing each number not considered ? In the worst case, we’ll have atleast floor(25/2)=12 division tests for each number. I think the expression of complexity is of the sort:
O( N * CostFactorization + T * NumUpdates * ExponentiationTime) so it will be O( N + T * lg(MAX))
can somebody give me the testcase for which i am getting sigfpe
my solution is:CodeChef: Practical coding for everyone
@khitish…int can not store such huge values(multiplication of all nos may reach upto 100 ^ 100000…some combination of nos may lead to ur b array storing a “0”…please go through the editorial to get an idea of what u have to do to solve this sum…!!!
the 25 prime logic was very good trick in this problem…otherwise TLe
can there be overflow in the cumulative frequency if each of it’s elements is int? Also when I logically declared my data-types i got WA solution1and when I changed everything to long long it got accepted solution2. Can any one please tell the reason or point out where is the overflow in the first program? Thanks in advance.
Again, posting here for help…
I’m stuck with this problem. For some test case no. > 100, it’s giving me SIGSEV runtime error…I’ve tried every corner case I can think of…still not getting any leads…
my logic is same as the editorial,but it gives TLE.
http://www.codechef.com/viewsolution/3914314
please can someone guide me where i might be wrong
please check submision id 4099624,it’s giving wrong answer… CodeChef: Practical coding for everyone please say why it’s wrong? On which test case it’s wrong ???
I have used precalculation technique . For ex. let 1 2 3 4 5 be array .
Then through precomputation i have made another array . 1 2 6 24 120 . After that in order to cal any query it is :- arra[m]/arr[l-1] where l is lower rage and m is upper … Is my approach wrong… getting WA many times Could someone help me out. Solution is :- CodeChef: Practical coding for everyone
Please help me out. Tried every optimization I could think of!
What is wrong with this code?
I am getting WA.
Will the segment tree approach work?
I tried but its giving WA.
can anyone help me with the following code. why is it not working i can’t see…please.
https://www.codechef.com/viewsolution/15878086