#include <iostream> // For cout, cin, & endl
#include <cmath> // For sqrt, ceil, min, & max
#include <ctime> // for clock_t, chrono
int gcd( int a,int b) {
int h;
for ( h = a< b? a: b; h >= 1 ; h-- ) {
if ( ( a% h == 0 ) && ( b% h == 0 ) )
break ;
}
return h;
}
int OPAlgo( int n1, int n2, int lcm, int hcf) {
int cnt = 0 ;
for ( int i = n1; i <= n2; i++ ) {
//checking if the number divides the lcm completely
if ( lcm% i == 0 ) {
int a = hcf * lcm / i; // its other multiplier
//checking if their gcd is equal to given hcf
if ( a <= n2 && a >= n1) {
int b = gcd( a, i) ; //finding their gcd
if ( b == hcf) {
int c = ( i* a) / b; //finding the lcm by a*b = lcm*hcf formula and
//checking
if ( c == lcm) {
cnt++ ;
}
}
}
}
}
return cnt;
}
int myGCD( int u, int v) {
int r;
while ( v ! = 0 ) {
r = u % v;
u = v;
v = r;
}
return u;
}
int numPairs( int n1, int n2, int lcm, int hcf) {
int count = 0 ;
int myProd = lcm * hcf;
// If sqrt(myProd) > n2, then we need to stop at n2
int myLim = std:: min ( ( int ) std:: sqrt ( ( double ) myProd) , n2) ;
// We ensure that we cover the entire range by taking the
// max. E.g. if n1 > myProd / n2, we would start at n1
double myStart = std:: max ( n1, myProd / n2) ;
myStart = std:: ceil ( myStart / ( double ) hcf) * hcf;
for ( int i = ( int ) myStart; i <= myLim; i + = hcf)
if ( lcm % i == 0 ) // ensure our number is divisible by lcm
if ( myGCD( i, myProd / i) == hcf) // ensure our pair gives correct gcd
++ count;
return count;
}
int main( ) {
int n1, n2, lcm, hcf, countNoOrder = 0 , countAll = 0 ;
std:: cin >> n1 >> n2 >> lcm >> hcf;
std:: clock_t start_time, end_time;
start_time = clock ( ) ;
for ( int i = n1; i < ( n1 + 500 ) ; ++ i)
countNoOrder + = numPairs( i, n2, lcm, hcf) ;
end_time = clock ( ) ;
std:: cout << "Time taken with modified algorithm numPairs : " <<
end_time - start_time << std:: endl ;
start_time = clock ( ) ;
for ( int i = n1; i < ( n1 + 500 ) ; ++ i)
countAll + = OPAlgo( i, n2, lcm, hcf) ;
end_time = clock ( ) ;
std:: cout << "Time taken with corrected OP algorithm : " <<
end_time - start_time << std:: endl ;
std:: cout << "Result for modified algo : " << countNoOrder << std:: endl ;
std:: cout << "Result for original OP code : " << countAll << std:: endl ;
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPiAvLyBGb3IgY291dCwgY2luLCAmIGVuZGwKI2luY2x1ZGUgPGNtYXRoPiAgICAvLyBGb3Igc3FydCwgY2VpbCwgbWluLCAmIG1heAojaW5jbHVkZSA8Y3RpbWU+ICAgIC8vIGZvciBjbG9ja190LCBjaHJvbm8KCmludCBnY2QoIGludCBhLGludCBiKXsKICAgIGludCBoOwogICAgZm9yKGggPSBhPGI/YTpiOyBoID49IDE7IGgtLSl7CiAgICAgICAgaWYoKGElaCA9PSAwKSAmJiAoYiVoID09IDApKQogICAgICAgICAgICBicmVhazsKICAgIH0KIAogICAgcmV0dXJuIGg7Cn0KIAppbnQgT1BBbGdvKGludCBuMSwgaW50IG4yLCBpbnQgbGNtLCBpbnQgaGNmKSB7CiAgICBpbnQgY250ID0gMDsKIAogICAgZm9yIChpbnQgaSA9IG4xOyBpIDw9IG4yOyBpKyspIHsKICAgICAgICAvL2NoZWNraW5nIGlmIHRoZSBudW1iZXIgZGl2aWRlcyB0aGUgbGNtIGNvbXBsZXRlbHkgIAogICAgICAgIGlmKGxjbSVpID09IDApewogICAgICAgICAgICBpbnQgYSA9IGhjZiAqIGxjbSAvIGk7Ly8gaXRzIG90aGVyIG11bHRpcGxpZXIKIAogICAgICAgICAgICAvL2NoZWNraW5nIGlmIHRoZWlyIGdjZCBpcyBlcXVhbCB0byBnaXZlbiBoY2YKICAgICAgICAgICAgaWYgKGEgPD0gbjIgJiYgYSA+PSBuMSkgewogICAgICAgICAgICAgICAgaW50IGIgPSBnY2QoYSwgaSk7Ly9maW5kaW5nIHRoZWlyIGdjZAogICAgICAgICAgICAgICAgaWYoYiA9PSBoY2YpewogICAgICAgICAgICAgICAgICAgIGludCBjID0gKGkqYSkgLyBiOy8vZmluZGluZyB0aGUgbGNtIGJ5IGEqYiA9IGxjbSpoY2YgZm9ybXVsYSBhbmQgCiAgICAgICAgICAgICAgICAgICAgLy9jaGVja2luZwogICAgICAgICAgICAgICAgICAgIGlmKGMgPT0gbGNtKXsKICAgICAgICAgICAgICAgICAgICAgICAgY250Kys7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogCiAgICByZXR1cm4gY250Owp9CiAKaW50IG15R0NEKGludCB1LCBpbnQgdikgewogICAgaW50IHI7CiAgICB3aGlsZSAodiAhPSAwKSB7CiAgICAgICAgciA9IHUgJSB2OwogICAgICAgIHUgPSB2OwogICAgICAgIHYgPSByOwogICAgfQogICAgcmV0dXJuIHU7Cn0KIAppbnQgbnVtUGFpcnMoaW50IG4xLCBpbnQgbjIsIGludCBsY20sIGludCBoY2YpIHsKIAogICAgaW50IGNvdW50ID0gMDsKICAgIGludCBteVByb2QgPSBsY20gKiBoY2Y7CiAKICAgIC8vIElmIHNxcnQobXlQcm9kKSA+IG4yLCB0aGVuIHdlIG5lZWQgdG8gc3RvcCBhdCBuMgogICAgaW50IG15TGltID0gc3RkOjptaW4oKGludCkgc3RkOjpzcXJ0KChkb3VibGUpIG15UHJvZCksIG4yKTsKIAogICAgLy8gV2UgZW5zdXJlIHRoYXQgd2UgY292ZXIgdGhlIGVudGlyZSByYW5nZSBieSB0YWtpbmcgdGhlCiAgICAvLyBtYXguIEUuZy4gaWYgbjEgPiBteVByb2QgLyBuMiwgd2Ugd291bGQgc3RhcnQgYXQgbjEKICAgIGRvdWJsZSBteVN0YXJ0ID0gc3RkOjptYXgobjEsIG15UHJvZCAvIG4yKTsKICAgIG15U3RhcnQgPSBzdGQ6OmNlaWwobXlTdGFydCAvIChkb3VibGUpIGhjZikgKiBoY2Y7CiAKICAgIGZvciAoaW50IGkgPSAoaW50KSBteVN0YXJ0OyBpIDw9IG15TGltOyBpICs9IGhjZikKICAgICAgICBpZiAobGNtICUgaSA9PSAwKSAgLy8gZW5zdXJlIG91ciBudW1iZXIgaXMgZGl2aXNpYmxlIGJ5IGxjbQogICAgICAgICAgICBpZiAobXlHQ0QoaSwgbXlQcm9kIC8gaSkgPT0gaGNmKSAgLy8gZW5zdXJlIG91ciBwYWlyIGdpdmVzIGNvcnJlY3QgZ2NkCiAgICAgICAgICAgICAgICArK2NvdW50OwogCiAgICByZXR1cm4gY291bnQ7Cn0KIAppbnQgbWFpbigpIHsKICAgIGludCBuMSwgbjIsIGxjbSwgaGNmLCBjb3VudE5vT3JkZXIgPSAwLCBjb3VudEFsbCA9IDA7CiAgICBzdGQ6OmNpbiA+PiBuMSA+PiBuMiA+PiBsY20gPj4gaGNmOwogICAgc3RkOjpjbG9ja190IHN0YXJ0X3RpbWUsIGVuZF90aW1lOwogICAgCiAgICBzdGFydF90aW1lID0gY2xvY2soKTsKICAgIGZvciAoaW50IGkgPSBuMTsgaSA8IChuMSArIDUwMCk7ICsraSkKICAgICAgICBjb3VudE5vT3JkZXIgKz0gbnVtUGFpcnMoaSwgbjIsIGxjbSwgaGNmKTsKICAgIGVuZF90aW1lID0gY2xvY2soKTsKCiAgICBzdGQ6OmNvdXQgPDwgIlRpbWUgdGFrZW4gd2l0aCBtb2RpZmllZCBhbGdvcml0aG0gbnVtUGFpcnMgOiAiIDw8CiAgICAgICAgZW5kX3RpbWUgLSBzdGFydF90aW1lIDw8IHN0ZDo6ZW5kbDsKICAgICAgICAKICAgIHN0YXJ0X3RpbWUgPSBjbG9jaygpOwogICAgZm9yIChpbnQgaSA9IG4xOyBpIDwgKG4xICsgNTAwKTsgKytpKQogICAgICAgIGNvdW50QWxsICs9IE9QQWxnbyhpLCBuMiwgbGNtLCBoY2YpOwogICAgZW5kX3RpbWUgPSBjbG9jaygpOwogICAgCiAgICBzdGQ6OmNvdXQgPDwgIlRpbWUgdGFrZW4gd2l0aCBjb3JyZWN0ZWQgT1AgYWxnb3JpdGhtIDogIiA8PAogICAgICAgIGVuZF90aW1lIC0gc3RhcnRfdGltZSA8PCBzdGQ6OmVuZGw7CiAgICAKICAgIHN0ZDo6Y291dCA8PCAiUmVzdWx0IGZvciBtb2RpZmllZCBhbGdvIDogIiA8PCBjb3VudE5vT3JkZXIgPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8ICJSZXN1bHQgZm9yIG9yaWdpbmFsIE9QIGNvZGUgOiAiIDw8IGNvdW50QWxsIDw8IHN0ZDo6ZW5kbDsKICAgIHJldHVybiAwOwp9Cgo=