Can't understand solution of MODEQ

I am trying to solve a problem which was in may long 2021 of MODEQ.
i watch codechef video editorial but can’t understand properly.

problem link: CodeChef: Practical coding for everyone

1 Like

For any integers x and m, x mod m lies between 0 and (m-1). Any number in this range modulo m will be that number itself.
Here a < b guarantees that (M mod a) mod b = M mod a. This is because M mod a will be less than a and hence also less than b.
Now we need M mod a = (M mod b) mod a which breaks down to (M - (M mod b)) mod a = 0. We can now iterate over all values of b and we have to find all values of a such that (M - M mod b) = 0 which means that a is a factor of (M - M mod b). Combine this with the condition a < b, you just have to find all factors of (M - M mod b) which are less than b. To do this factorize all numbers beforehand and use `stl::lower_bound`
There is also this extra case when M - M mod b is zero. In this case, a can take any value less than b.

``````using namespace std;
#include <bits/stdc++.h>
const int N = 5e5 + 3;
vector<int> fac[N];
void prep(){
for(int i = 1; i < N; i++){
for(int j = 1; i*j < N; j++){
fac[i*j].pb(i);
}
}
}
void testcase(){
int n,m;
cin >> n >> m;
ll ans = 0;
for(int b = 1; b <= n; b++){
int here = m - m%b;
if(here == 0)ans += b-1;
else{
ans += lower_bound(fac[here].begin(),fac[here].end(),b) - fac[here].begin(); // returns first value >= val
}
}
cout << ans << "\n";
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int tt = 1;prep();
cin >> tt;
while(tt--){
testcase();
}
return 0;
}
``````

thank you so much