My code worked for the sample testcase, but still getting WA. What is wrong with my code?
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
//typedef unsigned long long ll;
int main(){
ll t;
cin>>t;
while(t--)
{
ll n,a;
cin>>n>>a;
n = n*n;
ll M = 1000000007;
ll p=0,res=0;
for(int i=1;i<=n;i++)
{
ll temp = 2*i - 1;
p = (ll)(pow(a,temp)+0.5);
a = a*p;
n = n - temp;
res += p;
//cout<<temp<<" "<<p<<" "<<a<<" "<<n<<endl;
}
cout<<res%M<<endl;
}
}
why would you think about the negative power for this question.As the constraints give you only positive numbers then how can you get some negative power to calculate.
1 Like
Because you used inbuilt pow to find the powers it won’t give you the right answer for the constraints more than 10^9 and your answer will be wrong.Use function to calculate modular exponentiation.
1 Like
CodeChef: Practical coding for everyone.
Any test case on which this fails and why??
actually,for inputs t=1 and N=3 A=3, for 3 iteration pow(6561,5) is called leading to some negative values during this evaluation. I don’t know as to why my answer is coming wrong…probably this is the reason…please help
Great Explanation.Thanks @apurv3011. It is better than official editorials.Keep posting more video on CP…Sunscribed your channel…
1 Like
Guys I am getting WA, but the test case is running. Please have a look.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t!=0)
{
t–;
long long int a,n;
cin>>n>>a;
long long int prod[n];//store all p's in this array
long long int temp=0;
prod[0]=a;
for(int i=1;i<n;i++)
{
temp=(prod[i-1]*(int(pow(a,i))));
prod[i]=(pow(temp,(2*(i+1)-1)));
}
long long int sum=0;
for(int i=0;i<n;i++)
{
sum=(sum+prod[i])%(1000000007);
}
cout<<sum<<endl;
}
return 0;
}
I am taking modulus after adding one p to other for every p(i), but still it’s showing WA only.
I figured out the sequence easily. But was not sure how I would hold such a big number which increases substantially in each step. The answer is using powers. Thanks!
And this is amazing source.
1 Like
Time Complexity of modular exponentiation is O(logy). Now if you are changing power every time you are increasing time every time. rather what you can do is use the result calculated in last step to reduce the time. in first step,p1=a then p2=a^6, p3=a^40. So while calculating p3 you can use result calculated in p2. So you won’t be doing extra calculations
Then there may be something wrong in your logic of code. Try to dry run your code and point out the mistakes. 
I did bro. I added the modular function for power calculation, but still it’s not working. I added mod everywhere possible just to check but still it didn’t work, even though the test case ran every single time. Please have a look at my code 
#include<bits/stdc++.h>
using namespace std;
int power(long long int x, long long int y) //X^P MOD P
{
long long int res = 1;
long long int p=1000000007;
x = x % p;
if (x == 0) return 0;
while (y > 0)
{
if (y & 1)
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res%p;
}
int main()
{
int t;
cin>>t;
long long int p=1000000007;
while(t!=0)
{
t--;
long long int a,n;
cin>>n>>a;
//vector<vector<int>> v(n,vector<int> (n,a));
long long int prod[n];//store all p's in this array
long long int temp=0;
prod[0]=a;
for(int i=1;i<n;i++)
{
temp=(prod[i-1])*(power(a,i));
prod[i]=power(temp,(2*(i+1)-1));
}
long long int sum=0;
for(int i=0;i<n;i++)
{
sum=(sum+prod[i])%p;
}
cout<<sum<<endl;
}
return 0;
}
There is no problem with your power function, it worked perfectly.
Check out this main code.
unsigned long long ans=0;
long long count =1;
while(N–>0){
unsigned long long cal= selfPow(A,count) ;
cal = cal%1000000007;
ans = (ans+cal)%1000000007;
A = (Acal)%1000000007;*
count = count+2;
}
cout<<ans<<endl;
1 Like
Does CodeChef support BOOST library for C++ using which we can use cpp_int_ data type to fit in large numbers and do this question without “Fast Modulo Exonentiation” ?
integer overflow takes place in that case since the numbers grow bigger than the range of long long int. so take modulo at each step of exponentiation using a self defined function .
1 Like
Please help!! what am I doing wrong ? The power function is working fine but still getting wrong answer See this
Thanks bro. It worked. Maybe I was missing some mod operation in my main code. I will check it out.
Can anyone help me in finding the error in my code?
https://www.codechef.com/viewsolution/32133299
hello geeks,
Please have a look on my code, I am getting segmentation fault.
#include
#include <bits/stdc++.h>
#include
#include
using namespace std;
#define ll long long int
#define mod 1e9+7
ll fxp(ll a,ll b,ll m)
{
if(b==2)
return (aa)%m;
if(b%2==0)
return fmod(fxp(aa,b/2,m),mod);
return fmod(fxp(a,b-1,m)*a,mod);
}
void swap(ll &a,ll &b){ ll t=a; a=b; b=t;}
int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
ll n,A,s,res=0;
cin>>n>>A;
for(ll i=1;i<=n;i++)
{
s=fxp(A,2i-1,mod);
A=As;
res+=s;
res=fmod(res,mod);
}
cout<<res<<endl;
}
return 0;
}