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;
}