# CodeChef: May Long Challenge | Modular Equation | MODEQ | Solution

Share:

View on Codechef

Given integers NN and MM, find the number of ordered pairs (a,b)(a,b) such that 1≤a<b≤N1≤a<b≤N and ((M mod a) mod b)=((M mod b) mod a)((M mod a) mod b)=((M mod b) mod a).

### Input

• The first line contains an integer TT, the number of test cases. Then the test cases follow.
• The only line of each test case contains two integers NN, MM.

### Output

For each testcase, output in a single line the answer to the problem.

### Constraints

• 1≤T≤10001≤T≤1000
• 2≤N≤1062≤N≤106
• 1≤M≤5⋅1051≤M≤5⋅105
• The sum of NN over all test cases does not exceed 106106.

Note: Multiplier for JAVA for this problem is reduced to 1.251.25 instead of usual 22.

• 1≤T≤101≤T≤10
• 2≤N≤1032≤N≤103
• 1≤M≤1051≤M≤105

• 1≤T≤1001≤T≤100
• 2≤N≤1052≤N≤105
• 1≤M≤1051≤M≤105
• The sum of NN over all test cases does not exceed 106106.

Subtask #3 (50 points): Original Constraints

### Sample Input

``````3
3 5
3 6
3 10
``````

### Sample Output

``````2
3
2
``````

### Explanation

Test Case 11: The valid pairs are {(1,2),(1,3)}{(1,2),(1,3)}.

Test Case 22: The valid pairs are {(1,2),(1,3),(2,3)}{(1,2),(1,3),(2,3)}.

Test Case 33: The valid pairs are {(1,2),(1,3)}{(1,2),(1,3)}.

Solution:

``````#include
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_studio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--){
ll m,n;
ll count = 0;
vector mod(n+1,1);
for(ll a=2;a<=n;a++){
ll x=m%a;
count += mod[x];
for(ll b=x;b<=n;b+=a){
mod[b]++;
}
}
cout<<count<<endl;
}
return 0;
}``````