Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=5584

Give a coordinate (ex, ey), What points did you come from . The rule of going is x perhaps y Plus their least common multiple lcm(x, y).

consider (ex, ey) It's coming from other places , Let's go to (x,y) When ,gcd(x, y)=k,x=k*m1, y=k*m2.

The next step could be (x, y+x*y/gcd(x, y)) Or is it (x+x*y/gcd(x,y), y).

use k and m1,m2 To express as (k*m1, k*m2+m1*m2*k)=(k*m1, k*m2*(m1+1)), or (k*m1+m1*m2*k, k*m2)=(k*m1*(m2+1), k*m2).

I'll just focus on (k*m1*(m2+1), k*m2).m1 and m2 Mutual quality and (m2+1) And m2 Mutual quality .

that gcd(k*m1*(m2+1), k*m2)=k, That is, no matter what changes , Their greatest common factor is k. It also proves that the path is unique , What we're looking for is the number of possible starting positions , So think about it directly every time x The situation in lega ( namely y>x When , In exchange for x,y). We can (ex, ey) Push it back up .x'=k1*m1/(m2+1), When x No (y + k) After an integral multiple of , namely x/(k*(m2+1)) Not for 0 end .

 #include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; int ex, ey; int main() {
// freopen("in", "r", stdin);
int T, _ = ;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &ex, &ey);
int k = __gcd(ex, ey);
if(ex < ey) swap(ex, ey);
int ans = ;
while() {
if(ex % (ey + k) != ) break;
ans++;
ex = ex / (ey / k + );
if(ex < ey) swap(ex, ey);
k = __gcd(ex, ey);
}
printf("Case #%d: %d\n", _++, ans);
}
return ;
}

[HDOJ5584]LCM Walk( number theory , law ) More articles about

  1. HDU5584 LCM Walk number theory

    LCM Walk Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Su ...

  2. hdu-5584 LCM Walk( number theory )

    Topic link :LCM Walk Time Limit: 2000/1000 MS (Java/Others)     Memory Limit: 65536/65536 K (Java/Others)To ...

  3. L - LCM Walk HDU - 5584 ( number theory )

    Topic link : L - LCM Walk HDU - 5584 The main idea of the topic : First of all T Group test sample , And then give you x and y, This is the end point . And then ask how many starting points you can get to this x and y. The rule of every walk is (m1,m2) To (m1+ ...

  4. HDU 5584 LCM Walk mathematics

    LCM Walk Time Limit: 20 Sec Memory Limit: 256 MB Topic linking http://acm.hdu.edu.cn/showproblem.php?pid=5584 ...

  5. hdu 5584 LCM Walk( Mathematical derivation formula , law )

    Problem Description A frog has just learned some number theory, and can't wait to show his ability t ...

  6. HDU - 5584 LCM Walk ( number theory GCD)

    A frog has just learned some number theory, and can't wait to show his ability to his girlfriend. No ...

  7. HDU 5584 LCM Walk( mathematical problem )

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=5584 The question :(x, y) After one operation, it can become (x+z, y) or (x, y+z) Now I'll give you a little (ex, e ...

  8. hdu 5584 LCM Walk

    It's no use using a good formula ... It's easy to think about it , First of all, we should analyze , Because one at a time LCM Is greater than or equal to any of these numbers , Then I LCM Add to which number , That number is going to be big , Think so , We knew , Every (x,y) Corresponding to one kind of situation . ...

  9. 【HDU 5382】 GCD?LCM! ( number theory 、 Integrability function )

    GCD?LCM! Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total ...

Random recommendation

  1. Linux( Ten )___iptables A firewall

    One . The function of firewall 3、 ... and . Firewall classification 3、 ... and .iptables Basic grammar : surface : Commonly used filter,nat For address mapping . The configuration file : /etc/sysconfig/iptables Filter table information . see i ...

  2. linux Output /dev/null

    I'm learning Linux In the process of , You often see some terminal commands or programs with ">/dev/null 2>&1 " appear , Because we have met several times , To understand , Take time to Baidu or g ...

  3. windows to ping It requires extra times

    @echo off set /p host=host Address: set logfile=Log_%host%.log echo Target Host = %host% >%logfil ...

  4. LCM compatible

    1.project-1998-trunk-bootable-bootloader-lk-project:   Copy zaw1998aa_platform.mk by zaw2000aa_platform.mk ...

  5. Python 2.7 Installation (64 position win10)

    Python 2.7.12 Download address :https://www.python.org/downloads/release/python-2712/ The installation path D:\Program Files\Python ...

  6. POJ 2388 Who's in the Middle ( Fast selection algorithm :O(N) Finding the third order of a sequence K Big )

    [ The question ] Finding the middle term of a sequence . --- This can be extended to the second part of the sequence K term . The first time I did it, I sorted the water directly = =-- This time back to learn O(N) Fast selection algorithm for . The quick selection algorithm is based on the quick sort process , At each stage, we choose a number as the benchmark , and ...

  7. EF6 Calling stored procedure , Returns multiple result sets for processing

    link :http://www.codeproject.com/Articles/675933/Returning-Multiple-Result-Sets-from-an-Entity-Fram Case study : ...

  8. JBoss Series 69 :CDI Basic concepts

    summary if EJB,JPA Before JEE(JEE5 And JEE5 Before ) A landmark specification in , So in JEE6,JEE7 in CDI It's comparable to ,CDI(Contexts and Dependency Injectio ...

  9. The third chapter Netty Get started with Applications

    3.1 Netty Build the development environment 3.1.1 download Netty Software package 3.1.2 build Netty Application engineering 3.2 Netty Server development 3.3 Netty Client development 3.4 Operation and commissioning 3.4.1 clothing ...

  10. cocos creator The use of particle effects in

    Just like the star effect above , Produce special effects on touch , But it doesn't destroy nodes , Because it has to be used many times , So use the node pool NodePool Preserved . Here are some basic control functions to use when using particle effects : My use :