Did you by any chance do
2^(n*(n-1)/2 % mod) ?
Your answer is correct if they mentioned distinct.
@crap_the_coder Yes i think because each will generate new graph and in example output answer for n = 4 was 64
@everule1 Yes i applied same formula and it passed 5 out of 13 test cases, is it related to modular exponentiation…?
Im sorry, but that is wrong…
You can take %(mod -1)
I think you should read fermat’s little theorem
i know fermat’s little theorem but how is it useful in this case…??
Let 10^9 + 7 =p
Now say
You want 2^p+3
You take 2^3 =8 but 2^p+3 is 16 mod p
Because 2^p is 2 mod p.
But i have to take mod with overall value
i.e
let x = (n*(n-1))/2;
then what i was calculating is (2^x)%mod
Please just post the code you submitted, as best as you can remember it
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const ll MOD = 1e9 + 7;
ll powerLL(ll x, ll n)
{
ll ans = 1;
while (n) {
if (n & 1)
ans = ans * x % MOD;
n = n / 2;
x = x * x % MOD;
}
return ans;
}
ll powerStrings(string sa, string sb)
{
ll a = 0, b = 0;
for (int i = 0; i < sa.length(); i++)
a = (a * 10 + (sa[i] - '0')) % MOD;
for (int i = 0; i < sb.length(); i++)
b = (b * 10 + (sb[i] - '0')) % (MOD - 1);
return powerLL(a, b);
}
int main()
{
int n; cin>>n;
ll tmp = (n*(n-1))/2;
string p = to_string(tmp);
cout << powerStrings("2", p) << endl;
return 0;
}
Since n
is declared as an int
, this will overflow for sufficiently large n
: n=46342 should do the trick.
Lesson: Instead of trying to describe your code, just post it (preferably formatted for readability/ compilability)
i had tried to declare it long long int also but it didn’t helped much, so what should i have done here then …??
Declaring n
as long long int
would eliminate one source of error, and I can’t see any others offhand.
Edit:
Wait - why “- 1
” here?
b = (b * 10 + (sb[i] - '0')) % (MOD - 1);
Edit2:
Actually, you shouldn’t be taking the exponent modulo anything - just leave it alone.
Edit3:
Oh, I think I see. Hmmm … can’t find any further errors after you change n
to be long long int
.
Idk doesn’t give the right answer for 10^9 on codechef ide
What is the right answer? I get
2097152
but may have made a mistake.
Wait i forgot to change int to ll, I’m so sorry.
Shouldn’t he need to do modular division for the formula?
(I was looking at n*(n-1)/2 formula sorry)
For the division by 2
, do you mean? No, I don’t think so -
ll tmp = (n*(n-1))/2;
handles the division appropriately, I think.
There should be editorials for hiring challenges also