fork download
copy 
  1. #include <iostream> // For cout, cin, & endl
  2. #include <cmath>    // For sqrt, ceil, min, & max
  3.  
  4. int myGCD(int u, int v) {
  5.     int r;
  6.     while (v != 0) {
  7.         r = u % v;
  8.         u = v;
  9.         v = r;
  10.     }
  11.     return u;
  12. }
  13.  
  14. int numPairs(int n1, int n2, int lcm, int hcf) {
  15.  
  16.     int count = 0;
  17.     int myProd = lcm * hcf;
  18.  
  19.     // If sqrt(myProd) > n2, then we need to stop at n2
  20.     int myLim = std::min((int) std::sqrt((double) myProd), n2);
  21.  
  22.     // We ensure that we cover the entire range by taking the
  23.     // max. E.g. if n1 > myProd / n2, we would start at n1
  24.     double myStart = std::max(n1, myProd / n2);
  25.     myStart = std::ceil(myStart / (double) hcf) * hcf;
  26.  
  27.     for (int i = (int) myStart; i <= myLim; i += hcf)
  28.         if (lcm % i == 0)  // ensure our number is divisible by lcm
  29.             if (myGCD(i, myProd / i) == hcf)  // ensure our pair gives correct gcd
  30.                 ++count;
  31.  
  32.     return count;
  33. }
  34.  
  35. int main() {
  36.     int n1, n2, lcm, hcf, cnt;
  37.     std::cin >> n1 >> n2 >> lcm >> hcf;
  38.     cnt = numPairs(n1, n2, lcm, hcf);
  39.     std::cout << cnt << std::endl;
  40.     return 0;
  41. }
Success #stdin #stdout 0s 4176KB
comments (?)
stdin
copy 
100 7000 720720 12
stdout
copy 
9
https://ideone.com/q6axf2
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!