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” ?
Thanks
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.
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;
}
Hi! I have been stuck with this problem for quite some time now but couldn’t seem to figure out where the problem is. I tried a lot of test cases but failed to find where does it fail. Can someone please help me figure out the problem? This is my code:
#include <iostream>
using namespace std;
long long inf = 1000000007;
long long calPow(long long a, long long n){
long long temp;
if(n == 1){
return a;
}
long long t = calPow(a, n/2);
if(n & 1){
temp = t * t;
temp %= inf;
temp = temp * a;
temp %= inf;
return temp;
}
temp = t * t;
temp %= inf;
return temp;
}
int main(void) {
// your code goes here
int t;
cin >> t;
while(t--){
long long n, a;
cin >> n;
cin >> a;
long long p, sum = 0;
for(long long i = 1; i <= n; i++){
long long x = 2*i - 1;
p = calPow(a, x);
sum = (sum + p)%inf;
long long temp;
temp = a * p;
temp %= inf;
a = temp;
}
cout << sum;
}
return 0;
}can anyone help me solve this problem in python 3 , i solved it in c++ but not able to make the power function in python
#include
#include <math.h>
using namespace std;
int main() {
long long int i,j,n,t,x,p1,p2,sum;
cin>>t;
while(t–)
{
cin>>n>>x;
p1=x;
p2=1;
sum=0;
for(i=0;i<n;i++)
{
p1=(p1p2)%(1000000007);
p2=pow(p1,2i+1);
sum=sum+p2%(1000000007);
}
cout<<sum%(1000000007)<<"\n";
}
return 0;
}
im getting WA for this code please help