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 :wink:

1 Like

You can make it easier to understand by formatting your code :slightly_smiling_face:

1 Like

Please do the honors :relieved: @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!