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

Codechef

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.

Subtasks

Subtask #1 (10 points):

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

Subtask #2 (40 points):

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

See more posts here

Leave a Comment

Your email address will not be published. Required fields are marked *

x