using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ProgrammingContest { class MainClass : IDisposable { Scanner sc; Writer wr; string backPath = ".."; char dirSep = System.IO.Path.DirectorySeparatorChar; string inFilePath = null; string outFilePath = null; public MainClass() { this.inFilePath = this.backPath + this.dirSep + this.backPath + this.dirSep + "in.txt"; this.outFilePath = this.backPath + this.dirSep + this.backPath + this.dirSep + "out.txt"; } static void Main(string[] args) { using (var mainClass = new MainClass()) { //mainClass.MakeTestCase(); mainClass.Solve(); } } public void Dispose() { if (this.sc != null) { this.sc.Dispose(); this.sc = null; } if (this.wr != null) { this.wr.Dispose(); this.wr = null; } } void MakeTestCase() { Random rand = new Random(); var res = new StringBuilder(); using (var writer = new System.IO.StreamWriter(inFilePath)) writer.Write(res.ToString()); } void Solve() { this.wr = new Writer(this.isReactive); //this.wr = new Writer(this.outFilePath); #if DEBUG if (!this.isReactive) this.sc = new Scanner(this.inFilePath); else this.sc = new Scanner(); #else this.sc = new Scanner(); #endif long m = sc.NextLong; long n = sc.NextLong; long gcdVal = Gcd(m, n); m /= gcdVal; n /= gcdVal; long cnt = 0; // m/n while (m != n && m != 0 && n != 0) { if (m > n) { cnt += m / n; m %= n; } else if (m < n) { var tmp = m; m = n; n = tmp; cnt++; } } wr.WriteLine(Math.Max(0, cnt - 1)); } long Gcd(long a, long b) { if (a < b) { long tmp = b; b = a; a = tmp; } long ret = 1; while (b != 0) { ret = b; b = a % b; a = ret; } return ret; } bool isReactive = false; // TODO: reactive check !! } class Writer : IDisposable { System.IO.TextWriter writer; StringBuilder sb; bool isReactive; public Writer(string path) : this(new System.IO.StreamWriter(path)) { } public Writer(bool isReactive) : this(null, isReactive) { } public Writer(System.IO.TextWriter writer = null, bool isReactive = false) { this.writer = (writer ?? Console.Out); if (!(this.isReactive = isReactive)) { this.sb = new StringBuilder(); } } public void Dispose() { if (!isReactive) this.writer.Write(sb.ToString()); if (!this.writer.Equals(Console.Out)) this.writer.Dispose(); } public void Write(object val) { if (this.isReactive) { this.writer.Write(val.ToString()); this.writer.Flush(); } else this.sb.Append(val.ToString()); } public void Write(string format, params object[] vals) { if (this.isReactive) { this.writer.Write(format, vals); this.writer.Flush(); } else this.sb.AppendFormat(format, vals); } public void WriteLine(object val) { this.Write(val.ToString() + System.Environment.NewLine); } public void WriteLine(string format, params object[] vals) { this.Write(format + System.Environment.NewLine, vals); } } class Scanner : IDisposable { Queue buffer; char[] sep; System.IO.TextReader reader; public Scanner(string path) : this(new System.IO.StreamReader(path)) { } public Scanner(System.IO.TextReader reader = null) { this.buffer = new Queue(); this.sep = new char[] { ' ' }; this.reader = (reader ?? Console.In); } private void CheckBuffer() { if (this.buffer.Count == 0) { string str = null; while (string.IsNullOrEmpty(str)) { str = this.reader.ReadLine(); } string[] strArray = str.Split(this.sep); foreach (string elStr in strArray) { this.buffer.Enqueue(elStr); } } } public void Dispose() { if (!this.reader.Equals(Console.In)) this.reader.Dispose(); } public string Next { get { this.CheckBuffer(); return this.buffer.Dequeue(); } } public int NextInt { get { return int.Parse(this.Next); } } public double NextDouble { get { return double.Parse(this.Next); } } public long NextLong { get { return long.Parse(this.Next); } } public bool IsEmpty { get { this.CheckBuffer(); return this.buffer.Count == 0; } } } }