algorithm - Find a pair of intergers that can be reached to another pair using 4 operations -

-

given pair of integers (eg. (x,y)). want find whether possible convert them pair of integers using 4 operations, mentioned below, @ time number of times. operations follows:

(x,x+y) or (x+y,y) or (x-y,y) or (x,x-y)

for eg. (4,2) can converted (2,6) doing following operations:

(x-y,y) --- (2,2) (x,x+y) --- (2,4) (x,x+y) --- (2,6)

where (2,2) cannot converted (4,4). answer should yes or no.

claim: (x, y) can reach (z, w) if , if gcd(x, y) = gcd(z, w).

proof: (necessary) gcd(x, y) = gcd(x, x + y) = gcd(x + y, y) = gcd(x - y, y) = gcd(x, x - y). (sufficient) reachability symmetric. run euclidean algorithm reach (gcd(x, y), 0) (x, y).


Comments

Post a Comment

Popular posts from this blog

c# - Where does the .ToList() go in LINQ query result -

-
when getting data populate data grid, have pulled data, made list , mapped model, this: public list<person> getpeople() { var data = _db.person.tolist(); list<person> people = new list<person>(); foreach (var item in data) { person person = new person() { personid = item.personid, firstname = item.firstname, lastname = item.lastname }; people.add(person); } return people; } this works fine, in interest of writing less code discovered .select method , (what think is) anonymous type. have: public list<person> getpeople() { return _db.person.select(d => new person { personid = item.personid, firstname = item.firstname, lastname = item.lastname }).tolist(); } though not easy read, works fine too. there preference either way? ...
Read more

Listeners to visualise results of load test in JMeter -

-
i want run load test in non-gui mode , save results in .csv file. (i have not modified .properties files, standard information saved) i plan load file , visualise results jmeter’s listeners. which listeners suited purpose? should avoid @ cost, might cause me misinterpret information? (e.g. in view results tree response data empty have - - not saved this. however, there has in fact been response. if saw listener might think there hasn’t been one. since want avoid this, listeners have gain information needed .csv file.) i’d know both jmeter listeners plugins. if running test in non-ui mode ideally should disable listeners in script. use '-l' option store test results .jtl extension. can later open jtl file jmeter. aggregate report or summary report should summarize test results , response time , throughput. if want plot graphs see trends on test duration can use http://jmeter-plugins.org/#/ standard , lib set. i suggest following listeners: response ...
Read more

android - CollapsingToolbarLayout: position the ExpandedText programmatically -

-
i using new android support design view collapsingtoolbarlayout. have need position expandedtitle programmatically. actually way set position expandedtitle in .xml file (example here: https://goo.gl/l5h5fc ) there no public api set text position programmatically , fields private . do know if it's possible without reflection or 'hacky' tricks? i have solved problem exposing properties via reflection ( https://gist.github.com/fpezzato/8e7d45112883dbbc5ffb ), works don't use trick in production code. @google: please no more private or final stuff! :)
Read more