Header Ad

HackerEarth Plot the Curve problem solution

In this HackerEarth Plot, the Curve problem solution You are given with integers a,b,c,d,m. These represent the modular equation of a curve y*y mod m = (ax^3 + bx^2 + cx + d) mod m

Also, you are provided with an array A of size N. Now, your task is to find the number of pairs in the array that satisfy the given modular equation.

If (Ai,Aj) is a pair then Aj^2 mod m = (aAi^3 + bAi^2 + cAi + d) mod m.

Since the answer could be a very large output it modulo 10^9 + 7.


HackerEarth Plot the Curve problem solution


HackerEarth Plot the Curve problem solution.

#include <bits/stdc++.h>
#define M 1000000007
using namespace std;

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
long long a,b,c,d,m;
cin>>a>>b>>c>>d>>m;
int N;
cin>>N;
int arr[N];
unordered_map<int,long long> X,Y;
for(int i=0;i<N;i++)
{
cin>>arr[i];
long long x=((((((a*arr[i])%m)*arr[i])%m)*arr[i])%m+(((b*arr[i])%m)*arr[i])%m+(c*arr[i])%m+d%m)%m;
long long y=(arr[i]*arr[i])%m;
if(x<0)
x=m+x;
if(y<0)
y=m+y;
X[x]++;
Y[y]++;
}

long long ans=0;
for(auto it=X.begin();it!=X.end();it++)
ans=(ans + (it->second * Y[it->first])%M)%M;
cout<<ans<<endl;

}
}

Second solution

#include <bits/stdc++.h>

using namespace std;

const int md = 1E9 + 7;
const int N = 1E5 + 5;
long long ar[N];
map<long long, int> mp;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t --) {
long long a, b, c, d, m;
cin >> a >> b >> c >> d >> m;
int n;
cin >> n;
for(int i = 0; i < n; i ++) {
cin >> ar[i];
mp[(((ar[i] * ar[i]) % m) + m) % m] ++;
}
long long ans = 0;
for(int i = 0; i < n; i ++) {
long long x = (((((((a * ar[i]) % m) * ((ar[i] * ar[i]) % m)) % m) + (b * ((ar[i] * ar[i]) % m) % m) + ((c * ar[i]) % m) + d) % m) + m) % m;
if(mp.find(x) != mp.end())
ans += mp[x];
}
cout << (ans % md) << '\n';
mp.clear();
}
return 0;
}

Post a Comment

0 Comments