Can't understand solution of MODEQ

editorial
,
1

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
2

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

thank you so much