WA6 question gives wrong answer on using long long int in finding modular inverse but get AC when using int.Editorial for WA6 I have no clue why but I believe that this community has an answer.Thank u.
// Gives WA at testcase 6
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define PI (2*acos(0.0))
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define pos_rt_stbt(x) (__builtin_ffsll(x)) // return position of rightmost set bit ( 1 indexing ) pos_rt_stbt(10) = 2 ( 1010 )
#define ps(x,y) fixed<<setprecision(y)<<x
#define w(t) int t; cin>>t; while(t--)
#define nl "\n"
#define all(v) (v).begin(),(v).end()
#define clr(v) memset(v,0,sizeof(v));
#define sqr(x) ((x) * (x))
typedef long long ll;
//----------------------------------------------------------------------------------------------------------------------
// Fast Modular Exponentiation power(a,b,m) ==> (a to the power b) modulo m
template <typename T>
T power(T a, T b, T modulo)
{
if (b == 0)
return 1;
if (b == 1)
return a;
else {
T res = (power(a, b / 2, modulo) % modulo);
if (b % 2)
{
return ((((res % modulo) * (res % modulo)) % modulo) * (a % modulo)) % modulo;
}
else
{return ((res % modulo) * (res % modulo)) % modulo;}
}
}
ll mod_inv(ll a, ll mod) { return (power<ll>(a, mod - 2, mod)) % mod; }
int main()
{
std::chrono::time_point<std::chrono::high_resolution_clock> start_timer, end_timer;
start_timer = std::chrono::high_resolution_clock::now();
bool show_time = false; // change it to true when needed;
/* Building Block */
fast;
ll n, m;
cin >> n >> m;
ll d = mod_inv(n, m);
cout << d << nl;
end_timer = std::chrono::high_resolution_clock::now();
ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end_timer - start_timer).count();
if (show_time)
{cout << "\nElapsed Time: " << elapsed_time << "ms\n";}
return 0;
}
// This gets accepted , I just changed, typedef int ll
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define PI (2*acos(0.0))
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define pos_rt_stbt(x) (__builtin_ffsll(x)) // return position of rightmost set bit ( 1 indexing ) pos_rt_stbt(10) = 2 ( 1010 )
#define ps(x,y) fixed<<setprecision(y)<<x
#define w(t) int t; cin>>t; while(t--)
#define nl "\n"
#define all(v) (v).begin(),(v).end()
#define clr(v) memset(v,0,sizeof(v));
#define sqr(x) ((x) * (x))
typedef int ll;
//----------------------------------------------------------------------------------------------------------------------
// Fast Modular Exponentiation power(a,b,m) ==> (a to the power b) modulo m
template <typename T>
T power(T a, T b, T modulo)
{
if (b == 0)
return 1;
if (b == 1)
return a;
else {
T res = (power(a, b / 2, modulo) % modulo);
if (b % 2)
{
return ((((res % modulo) * (res % modulo)) % modulo) * (a % modulo)) % modulo;
}
else
{return ((res % modulo) * (res % modulo)) % modulo;}
}
}
ll mod_inv(ll a, ll mod) { return (power<ll>(a, mod - 2, mod)) % mod; }
int main()
{
std::chrono::time_point<std::chrono::high_resolution_clock> start_timer, end_timer;
start_timer = std::chrono::high_resolution_clock::now();
bool show_time = false; // change it to true when needed;
/* Building Block */
fast;
ll n, m;
cin >> n >> m;
ll d = mod_inv(n, m);
cout << d << nl;
end_timer = std::chrono::high_resolution_clock::now();
ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end_timer - start_timer).count();
if (show_time)
{cout << "\nElapsed Time: " << elapsed_time << "ms\n";}
return 0;
}
I have no idea what’s going on, there: your AC solution, for the following test input:
976917041 997137511
gives the answer k=
-518283967
when the question states that k \ge 1.
Maybe I don’t understand the Problem 
:
1 Like
oooh i get it now, vasya’s solution is incorrect because she used int instead of long long,
and they have asked us to submit the wrong code. (the same mistake that vasya would have made which is overflow int).
so basically wrong answer was expected int this problem 
6 Likes
yeah , I got that now. AC soln is actually the wrong soln . The problem asked for wrong solution indeed .BTW thanks for your help bro.
3 Likes
Thanks bro!
1 Like