fork download
copy 
  1. #include <iostream> // For cout, cin, & endl
  2. #include <cmath>    // For sqrt, ceil, min, & max
  3. #include <ctime>    // for clock_t, chrono
  4.  
  5. int gcd( int a,int b){
  6.     int h;
  7.     for(h = a<b?a:b; h >= 1; h--){
  8.         if((a%h == 0) && (b%h == 0))
  9.             break;
  10.     }
  11.  
  12.     return h;
  13. }
  14.  
  15. int OPAlgo(int n1, int n2, int lcm, int hcf) {
  16.     int cnt = 0;
  17.  
  18.     for (int i = n1; i <= n2; i++) {
  19.         //checking if the number divides the lcm completely  
  20.         if(lcm%i == 0){
  21.             int a = hcf * lcm / i;// its other multiplier
  22.  
  23.             //checking if their gcd is equal to given hcf
  24.             if (a <= n2 && a >= n1) {
  25.                 int b = gcd(a, i);//finding their gcd
  26.                 if(b == hcf){
  27.                     int c = (i*a) / b;//finding the lcm by a*b = lcm*hcf formula and 
  28.                     //checking
  29.                     if(c == lcm){
  30.                         cnt++;
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.     }
  36.  
  37.     return cnt;
  38. }
  39.  
  40. int myGCD(int u, int v) {
  41.     int r;
  42.     while (v != 0) {
  43.         r = u % v;
  44.         u = v;
  45.         v = r;
  46.     }
  47.     return u;
  48. }
  49.  
  50. int numPairs(int n1, int n2, int lcm, int hcf) {
  51.  
  52.     int count = 0;
  53.     int myProd = lcm * hcf;
  54.  
  55.     // If sqrt(myProd) > n2, then we need to stop at n2
  56.     int myLim = std::min((int) std::sqrt((double) myProd), n2);
  57.  
  58.     // We ensure that we cover the entire range by taking the
  59.     // max. E.g. if n1 > myProd / n2, we would start at n1
  60.     double myStart = std::max(n1, myProd / n2);
  61.     myStart = std::ceil(myStart / (double) hcf) * hcf;
  62.  
  63.     for (int i = (int) myStart; i <= myLim; i += hcf)
  64.         if (lcm % i == 0)  // ensure our number is divisible by lcm
  65.             if (myGCD(i, myProd / i) == hcf)  // ensure our pair gives correct gcd
  66.                 ++count;
  67.  
  68.     return count;
  69. }
  70.  
  71. int main() {
  72.     int n1, n2, lcm, hcf, countNoOrder = 0, countAll = 0;
  73.     std::cin >> n1 >> n2 >> lcm >> hcf;
  74.     std::clock_t start_time, end_time;
  75.  
  76.     start_time = clock();
  77.     for (int i = n1; i < (n1 + 500); ++i)
  78.         countNoOrder += numPairs(i, n2, lcm, hcf);
  79.     end_time = clock();
  80.  
  81.     std::cout << "Time taken with modified algorithm numPairs : " <<
  82.         end_time - start_time << std::endl;
  83.  
  84.     start_time = clock();
  85.     for (int i = n1; i < (n1 + 500); ++i)
  86.         countAll += OPAlgo(i, n2, lcm, hcf);
  87.     end_time = clock();
  88.  
  89.     std::cout << "Time taken with corrected OP algorithm : " <<
  90.         end_time - start_time << std::endl;
  91.  
  92.     std::cout << "Result for modified algo : " << countNoOrder << std::endl;
  93.     std::cout << "Result for original OP code : " << countAll << std::endl;
  94.     return 0;
  95. }
  96.  
  97.  
Success #stdin #stdout 3.01s 4180KB
comments (?)
stdin
copy 
10000 500000 8648640 120
stdout
copy 
Time taken with modified algorithm numPairs : 408
Time taken with corrected OP algorithm : 3006723
Result for modified algo : 3000
Result for original OP code : 6000
https://ideone.com/vmS8Go
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!