# Another method for MODEQ

Does anyone have any other understandable solution for MODEQ from May Long?

``````#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
long long t;
cin>>t;
while(t--){
long long n,anothernum;
cin>>n>>anothernum;
long long rocketscience=0;
vector <long long > vec(n+1,1);
for(long long i=2;i<=n;i++){
long long a=anothernum%i;
rocketscience+=vec[a];
for(long long  j=a;j<=n;j+=i){
vec[j]++;
}
}
cout<<rocketscience<<endl;
}
return 0;
}
``````

This is simple and easy to understand.

1 Like

Hope this helps

1 Like

You can make it easier to understand by formatting your code

1 Like

Please do the honors @manvi_03

Thanks this works
It would be better if you could explain this or share some reference to understand this

Iâ€™ll explain the idea with an example

let N=7 and M=47

say for 2 - (2,3), (2,4), (2,5), (2,6), (2,7) are interested ordered pairs

for each values like this for 1,3,4,5,6 if we find all ordered pairs, this is the brute O(N^2)

how do we optimize it ?

intuition is,

M%a%b == M%b%a

reduce it by fixing the ordered pairs (2,3), (2,4), (2,5), (2,6), (2,7),

M%2%b == M%b%2 (fixing â€˜aâ€™ as 2 in our ordered pairs)

LHS :-

since possible values of â€˜bâ€™ (3,4,5,6,7) here will always be greater than 2

we can for sure say LHS is to output what M%2 outputs here, which is M%2 = 47%2 = 1

why ?

0%(3 or 4 or 5 or 6 or 7) gives 0 always
1%(3 or 4 or 5 or 6 or 7) gives 1 always

RHS :-

now problem reduces to, we need RHS to match LHSâ€™s value 1,

i.e. (M%b)%2 = 1 what are the possible values of â€˜bâ€™ which can give me this output

if M%b outputs 1, 3, 5 (bounded by N=7, as values >= 7 are not possible remainders)

(1 or 3 or 5)%2 = 1 in all cases which matches our LHS

so we can achieve this by having a track of all our M%x count, where 1<=x<=N candidates for a,b

note 1 : while counting we should reduce one count for M%b%2 where (M%b) is 1 as we seek values of b greater than 2 ie. 3,4,5,6,7 which gives remainders 1,3,5,7
note 2 : once done with ordered pairs fixed a=2 we reduce the count in the mod table for M%a = M%2 = 47%2 = 1 so that it doesnâ€™t affect further ordered pairs

Time complexity is O(N * log(N))

for each [1-N] we do log(N) operation

how log(N) ? ans since we do 1 + 1/2 + 1/3 + â€¦ + 1/N ~ log(N) operations

``````private long solution(int N, int M) {

int[] mod_table = new int[N];

for (int i=1;i<=N;i++) {
mod_table[M%i]++;
}

long count = 0;
for (int i=1;i<=N;i++) {
int val = M%i;
mod_table[val]--;
for (int j=val;j<N;j=j+i) {
count += mod_table[j];
}
}

return count;
}``````

Done!