 # MODEQ - Editorial

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

Easy

# PREREQUISITES

Binary Search, Basic maths would do.

# PROBLEM

Given N and M, find the number of ordered pairs (a, b) such that 1 \leq a < b \leq N and ((M \bmod a) \bmod b) = ((M \bmod b) \bmod a)

# QUICK EXPLANATION

• For a given a, only b for which above equation holds is when M - M \bmod a is divisible by b and b < a
• We can precompute factors of all possible M in sorted order, in order to count such b by binary searching for each a.

# EXPLANATION

Since N is small, we can try all pairs (a, b) and check the condition, counting the pairs for which the condition is satisfied. This solution works in O(N^2) time, which is sufficient for subtask 1.

### Some Math

We can no longer try all pairs. Let’s focus on the condition.

((M \bmod a) \bmod b) = ((M \bmod b) \bmod a)
Since a < b, ((M \bmod a) \bmod b) = M \bmod a

Hence, (M \bmod a) = ((M \bmod b) \bmod a) is what we need.

Writing M = b * \lfloor \frac{M}{b} \rfloor + M\bmod b, we need (b * \lfloor \frac{M}{b} \rfloor + M\bmod b) \bmod a = ((M \bmod b) \bmod a)

((b * \lfloor \frac{M}{b} \rfloor) \bmod a = 0

Hence, we need T = M-M \bmod b to be divisible by a.

• If M < b, all 1 \leq a < b are valid.
• Only the factors of T = M-M \bmod b strictly smaller than b are valid candidates for a

We can now try all values of b one by one and compute T = M - M \bmod b. Now, we need to count the number of factors of T strictly less than b. We find all factors of T in O(\sqrt T) time.

The time complexity of this approach is O(N * \sqrt M)

Here, the time taken to factorize is too much. But the range of values is limited. If we have list of factors of all numbers from 1 to max(M) in sorted order, all we care about is finding the number of factors of X less than some value Y.

This can be answered by binary searching on the list containing factors of X, for the first element \geq y.

The construction of these lists take O(M*log(M)) time in a sieve style manner, as depicted by following pseudocode

factors[i] -> list of factors of i
for 1 <= i <= M:
j = i
while j <= M:
j += i


For answering queries, for each b, we need to do binary search on list containing factors of M-M \bmod b

The time complexity of this approach is O(M*log(M) + N*log(M))

# TIME COMPLEXITY

The time complexity is O(log(M) * (M + \sum N))

# SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;

const int maxt = 1e3, maxn = 1e6, maxm = 1e6;
const int maxs = 5e5;
vector<int> v[maxs + 1];
int main()
{
for(int i = 1; i <= maxs; i++){
for(int j = i; j <= maxs; j += i){
v[j].pb(i);
}
}
int t; cin >> t;
while(t--){
int n, m; cin >> n >> m;
ll ans = 0;
for(int a = 2; a <= min(n, m); a++){
int x = a * (m / a);
int l = 0, r = v[x].size() - 1;
while(l <= r){
int m = (l + r) >> 1;
if(v[x][m] < a){
l = m + 1;
}else{
r = m - 1;
}
}
}
for(int a = m + 1; a <= n; a++){
ans += a - 1;
}
cout << ans << endl;
}
}

Tester's Solution
import java.util.*;
import java.io.*;
class MODEQ{
//SOLUTION BEGIN
int maxM = (int)5e5;
int[] spf;
int[][] factors;
void pre() throws Exception{
spf = spf(maxM);
int[] count = new int[1+maxM];
for(int i = 1; i<= maxM; i++){
for(int j = i; j<= maxM; j+= i){
count[j]++;
}
}
factors = new int[1+maxM][];
for(int i = 1; i<= maxM; i++){
factors[i] = new int[count[i]];
count[i] = 0;
}
for(int i = 1; i<= maxM; i++){
for(int j = i; j<= maxM; j+= i){
factors[j][count[j]++] = i;
}
}
}
void solve(int TC) throws Exception{
int N = ni(), M = ni();
long ans = 0;
for(int b = 2; b <= N; b++){
int T = M%b;
//Find number of a such that M%a == T%a
//(M-T) is a multiple of a
//candidates for a are all a such that a < b and a|(M-T)
if(M == T){
ans += b-1;
continue;
}
int V = M-T;
int[] fact = factors[V];
int lo = 0, hi = fact.length-1;
while(lo < hi){
int mid = lo+(hi-lo+1)/2;
if(fact[mid] < b)lo = mid;
else hi = mid-1;
}
ans += lo+1;
}
pn(ans);
}
int[] factors(int[] spf, int x){
int[] factor = new int[]{1};
while(x > 1){
int p = spf[x], cnt = 0;
for(;x%p == 0; x/= p)cnt++;
int[] tmp = Arrays.copyOf(factor, (1+cnt)*factor.length);
for(int pw = 1, cur = p; pw <= cnt; pw++, cur *= p)
for(int i = 0; i< factor.length; i++)
tmp[pw*factor.length+i] = factor[i]*cur;
factor = tmp;
}
return factor;
}
int[] spf(int max){
int[] spf = new int[1+max];
for(int i = 2; i<= max; i++)
if(spf[i] == 0)
for(int j = i; j <= max; j += i)
if(spf[j] == 0)
spf[j] = i;
return spf;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MODEQ().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always. 10 Likes

I think this was a very nice counting problem. I modeled the problem as below.
Construct array g of size n containing nonzero elements where g[i] = m-m \pmod i. This is \mathcal O(n) time. Now the problem is to efficiently answer queries of the form, given integer a find the number of multiples of a in the subarray g[a+1, ~n].
To compute this we can first of all compute the factors of all numbers from
1 to 5\cdot10^5 fast using sieve like idea. Now we can create 2 arrays cnt and cur of size n. We start traversing the array and for each factor of g[i] we append the count value. Basically for all v \mid g[i] we do cnt[v]+=1. Also at the i'th stage we set cur[i] = cnt[i]. So after this cur[i] stores the number of multiples of i in subarray g[1, i] and cnt[i] stores the same for the subarray g[1, n]. So we have answered out queries in \mathcal O(1) after a \mathcal O(n) precomputation as the answer is just cnt[i]-cur[i]. So the answer is A = \sum \limits_{i=1}^{n} cnt[i]-cur[i]. But this is wrong. We have still not accounted for the zero elements in g. But that part of the problem we can do in \mathcal O(1) which is left as an exercise to the reader.(mainly because I don’t want to write it out)

4 Likes

1 Like

Hey, I guess time complexity can be reduced to O(M*logM + sum(N)), by dynamic handling of sieve.

2 data structures:

1. sieve for calculating number of factors (dynamically)
2. a list associated to every integer i. it will not contain multiples of i, rather the number of factors of that multiple, preceeding i

Say for i, we run over jth multiple of i: i*j
then we can check for the previous number of factors of i*j (say k), and can insert this into the list…(so we insert k into the ith list)

Now, for each test case for b, if we need say number of factors of b(M/b) which are less than b, we have it stored in list[b][M/b]…hence will take O(1)

2 Likes

how (b*floor(m/b))mod a==0 when m>b and a<b
for example if m=15 and b=10 and a=9 so from this formulat it is not satiesfied.

(10*floor(15/10))%9 is not equal to zero.

1 Like

What is the space-complexity for pre-computing all the factors?

Why time complexity for Java was 1.25 instead of 2? Is there any special method to solve it in Java?

here the equation (b*floor(m/b))mod a==0 is result of the condition (m%a)%b == (m%b)%a
you can verify that for m = 15 , a = 9, b = 10 the equation (m%a)%b == (m%b)%a is not satisfied .

O(m*m) approx

Can someone tell me how is this true?

1 Like

mlogm (~10^7), which is asymptotic sum of (m/i), for i=1 to i=m
( (m/i) is num. of multiples of i)
and hence is the same as the total space for divisors

2 Likes

That’s not true we have find such a and b which satisfy this condition that was the whole question in a nutshell.
Now if you are asking how did the formulae come up then here it is:
Since a<b so ((M mod a)modb) is nothing but (M mod a) since the remainder on dividing M by a is smaller than a always and hence is smaller than b for sure.
So now we have M mod a= (M mod b)mod a . which we can write as (M-Mmodb)moda.Now if you can see clearly M-Mmodb is nothing but dividend-remainder or mathematically something like dividend=quotient x num+remainder.So M-Mmodb is a factor of b as we r just removing the remainder from it. so M-Mmodb can be written as b*(M/b).
I hope this helps.

5 Likes

This part nothing but divisor*quotient part.

2 Likes

One optimization would be to avoid binary search, and just maintain the number of factors already counted and go on taking on from there only to count more factors less than current number.

Also, we don’t need to go beyond M, as if b > M, then M mod b = M and there a would be just b - 1. as any a < b, would satisfy M mod a = (M mod b) mod a = M mod a .
So, time complexity would be M log M + M, so N could be large.

2 Likes

I have seen the approach in editorial and understood it, apart from it i have seen people submitting a code which i couldn’t understand , can someone please help me in this .
Here is the code :

#include <vector>
#include <iostream>
using namespace std;
#define ll long long

int main()
{
ll t;
cin >> t;
while(t-- > 0)
{
ll n,m;
cin >> n >> m;
ll counter=0;
vector<ll> mxn(n+1,1);
for(ll ctr = 2; ctr<=n; ++ctr)
{
ll a = m%ctr;
counter+=mxn[a];
for (ll j=a;j<=n;j+=ctr) {
mxn[j]++;
}
}
cout << counter << endl;
}
return 0;


}
I wanted to understand the underlying logic of this code and proof of why its working. Looking forward to the community: 5 Likes

So what you’re saying is that you did not understand the approach used in this solution, yet you have an AC solution with this same approach during the contest. Got anything to say?

https://www.codechef.com/viewsolution/46261319

I saw this problem ,and find it similar to above. I understood it , but just wanted to get some more insight on it.

1 Like

Ok then, I’ll try to explain as much as I can. First of all, a counter array of all Mod values is made, i.e. the indexes of the array denote the mod answer. So, with the counter array , you basically are calculating all the pairs that end up at that index and in every iteration, with incrementing a sum value by mxn[a], you’ll be able to sum up all pairs.

2 Likes

Thanks ,can u suggest some similar problems for practise if u have?

As much as I’d love to, I can’t seem to remember any from the top of my head. Sorry man. 1 Like