First of all update us about the prizes for march grand contest. We did not receive any info regarding that.

Submissions of D will be rejudged, right?

When will the editorials be posted?

Why have you changed the problem statement of C? I think even the previous statement was fine, the answer should be the same?

Problem E is on stackexchange.

problem C can be done in $$$q * [sqrt(N) + sqrt(M)]$$$

My approach was basically at first I formed the equation

$$$(y1 + q * B) \ mod \hspace{2mm} M = y2$$$

Which can be rewritten like this

$$$M * q' + (-B) * q = y1 - y2$$$

This is a linear diophantine equation and one can obtain the general form of pair solutions which is mentioned on the linear diophantine equations page of CP-Algorithms.

https://cp-algorithms.com/algebra/linear-diophantine-equation.html

Observation :- If we plug the values corresponding to the general solution $$$x, y$$$ one can notice that only checking the usual gcd condition for linear diophantine equations does it and we won't have to deal with any range checks or anything.

So now our problem is basically checking if $$$x1 - x2$$$ is divisible by $$$gcd(n, i)$$$ where $$$i$$$ lies from $$$1$$$ to $$$n - 1$$$.

To solve it fast we can precompute gcds and then in sqrt time compute answers independently for $$$X$$$ and $$$Y$$$. Finally we multiply them and get our answer.

There is an edge case if the difference between $$$x1 - x2$$$ comes out to be $$$0$$$.

#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define Forl(i,a,b) for(ll (i)=(a);(i) < (b); ++(i))
#define Forn(i,a,b) for(int (i)=(a);(i) >= (b); --(i))
#define Fornl(i,a,b) for(ll (i)=(a);(i) >= (b); --(i))

ll n,m;
    cin>>n>>m;
    vector <ll> cnt(maxn),dnt(maxn);

    Forl(i,1,m) {
        cnt[__gcd(m, i)] += 1;
    }
    //Forl(i,1,m)cout<<cnt[i]<<endl;
    Forl(i,1,n) {
        dnt[__gcd(n, i)] += 1;
    }


    ll T;
    cin>>T;

    while(T--)
    {
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        ll x = 0, y = 0;

        

        ll p = abs(y1 - y2), q = abs(x1 - x2);

        if (p != 0) {
            for(ll i = 1; i * i <= p; i++) {
                if (p % i == 0) {
                    x += cnt[i];
                   // cout<<x<<endl;
                    if (p / i != i)x += cnt[p / i];
                }
            }
        } else 
            x = m - 1;

        if (q != 0) {
            for(ll i = 1; i * i <= q; i++) {
                if (q % i == 0) {
                    y += dnt[i];
                    //cout<<y<<endl;
                    if (q / i != i)y += dnt[q / i];
                }
            }
        } else 
         y = n - 1;

        cout<<x * y<<endl;
    }

Code for Reference

Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).