Given n, m, A and B. The task is to count the number of pairs of integers (x, y) such that 1 
x n and 1 y m and (x+y) mod A and (x+y) mod B both equals to 0.
Examples:
Input: n = 60, m = 90, A = 5, B = 10
Output: 540Input: n = 225, m = 452, A = 10, B = 15
Output: 3389
Approach: If (x+y) is divisible by both A and B then basically LCM of A and B is the smallest divisor of (x+y). So we calculate all numbers that is less than or equal to m and divisible by LCM of them and when iterating with the loop then we check if the present number is divisible by LCM of A and B.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to find the LCMint find_LCM(int x, int y){ return (x * y) / __gcd(x, y);}// Function to count the pairsint CountPairs(int n, int m, int A, int B){ int cnt = 0; int lcm = find_LCM(A, B); for (int i = 1; i <= n; i++) cnt += (m + (i % lcm)) / lcm; return cnt;}// Driver codeint main(){ int n = 60, m = 90, A = 5, B = 10; cout << CountPairs(n, m, A, B); return 0;} |
Java
//Java implementation of above approachimport java.util.*;public class ACE { static int gcd(int a,int b) { return b==0 ? a :gcd(b,a%b); } //Function to find the LCM static int find_LCM(int x, int y) { return (x * y) / gcd(x, y); } //Function to count the pairs static int CountPairs(int n, int m, int A, int B) { int cnt = 0; int lcm = find_LCM(A, B); for (int i = 1; i <= n; i++) cnt += (m + (i % lcm)) / lcm; return cnt; } //Driver code public static void main(String[] args) { int n = 60, m = 90, A = 5, B = 10; System.out.println(CountPairs(n, m, A, B)); }} |
Python 3
# Python3 implementation of# above approach# from math lib import gcd methodfrom math import gcd# Function to find the LCM def find_LCM(x, y) : return (x * y) // gcd(x, y)# Function to count the pairs def CountPairs(n, m, A, B) : cnt = 0 lcm = find_LCM(A, B) for i in range(1, n + 1) : cnt += (m + (i % lcm)) // lcm return cnt# Driver code if __name__ == "__main__" : n, m, A, B = 60, 90, 5, 10 print(CountPairs(n, m, A, B))# This code is contributed# by ANKITRAI1 |
C#
// C# implementation of above approachusing System;class GFG{ static int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); } // Function to find the LCM static int find_LCM(int x, int y) { return (x * y) / gcd(x, y); } //Function to count the pairs static int CountPairs(int n, int m, int A, int B) { int cnt = 0; int lcm = find_LCM(A, B); for (int i = 1; i <= n; i++) cnt += (m + (i % lcm)) / lcm; return cnt; } // Driver code public static void Main() { int n = 60, m = 90, A = 5, B = 10; Console.WriteLine(CountPairs(n, m, A, B)); }}// This Code is contributed by mits |
PHP
<?php// PHP implementation of above approachfunction gcd($a, $b){ return $b == 0 ? $a : gcd($b, $a % $b);}// Function to find the LCMfunction find_LCM($x, $y){ return (int)(($x * $y) / gcd($x, $y));}// Function to count the pairsfunction CountPairs($n, $m, $A, $B){ $cnt = 0; $lcm = find_LCM($A, $B); for ($i = 1; $i <= $n; $i++) $cnt += (int)(($m + ($i % $lcm)) / $lcm); return $cnt;}// Driver code$n = 60; $m = 90; $A = 5; $B = 10;echo CountPairs($n, $m, $A, $B);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>//Javascript implementation of above approach function gcd(a,b) { return b==0 ? a :gcd(b,a%b); } //Function to find the LCM function find_LCM(x,y) { return Math.floor((x * y) / gcd(x, y)); } //Function to count the pairs function CountPairs(n,m,A,B) { let cnt = 0; let lcm = find_LCM(A, B); for (let i = 1; i <= n; i++) cnt += Math.floor((m + (i % lcm)) / lcm); return cnt; } //Driver code let n = 60, m = 90, A = 5, B = 10; document.write(CountPairs(n, m, A, B)); // This code is contributed by rag2127</script> |
Output:
540
Time Complexity: O(n) for iterating from 1 till n.
Auxiliary Space: O(1) as no extra space is used.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
