but it gives me wrong answer,the only difference is that when calculating the value of add we need to apply mod;and the correct solution is as follows:
how will we know where to apply a mod operator…pls help.
but even though i do not use pow it shows wrong answer because in the answer they applied mod while calculating power of 7.how will i know that i should apply mod there.
" you can apply mod without making the answer wrong," does this mean that whenever we are asked to find answer modulo some number we can apply mod to every integer useful in calculating answer .
Broadly - if the answer involves adding, multiplying, subtracting (but not dividing) those numbers, then you should be able to apply mod to those numbers.
@anon62013538
The value of pow(7, count) cross the maximum limit of unsigned long long i.e, pow(7, count) > 1e19. Hence, you should use modular power function. Something like this:
ll powmod(ll a, ll b) {
ll res = 1;
a %= mod;
assert(b >= 0);
for (; b; b >>= 1) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
Your AC Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) a.begin(), a.end()
#define w(a) cerr << #a << " : " << (a) << "\n";
const ll mod = 1000000007;
ll powmod(ll a, ll b) {
ll res = 1;
a %= mod;
assert(b >= 0);
for (; b; b >>= 1) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
int main() {
ll n;
cin>>n;
ll count=1,sum=0;
while(n>0){
ll temp=n%2;
ll add=(powmod(7,count)*temp);
sum=(sum%mod+add%mod)%mod;
n/=2;
count++;
}
cout<<sum;
return 0;
}
