Algorithm - Problem - [上海赛前集训] 坐标跳跃

[上海赛前集训] 坐标跳跃

问题描述

在一个平面坐标系上,小明的初始位置坐标为 (p,q)(p,q),我们可以通过一次操作将他的位置变为 (p+q,q)(p+q,q)(p,p+q)(p, p+q)

给定一正整数 nn,小明的初始位置为 (1,1)(1, 1),问最少需要多少次操作,可变为一个新的坐标 (x,y)(x, y),且其中的 xxyy 至少有一个数字为 nn

输入

输入文件 coordinate.in
第一行一个正整数 nn

输出

输出文件 coordinate.out
一个整数表示答案

样例输入
1
7
样例输出
1
4
提示

30%30\%的数据, n1000n\leqslant 1000

60%60\%的数据, n2×104n\leqslant 2\times 10^4

100%100\%的数据,1n1061\leqslant n\leqslant 10^6

数论相关

分析

观察变换,不难发现,若 gcd(p,q)=1\gcd(p,q)=1 则有 gcd(p+q,q)=1\gcd(p+q,q)=1.
则最终含有 nn 的坐标 (x,n)(x,n) 中,也必有 gcd(x,n)=1\gcd(x,n)=1.
而从 (1,1)(1,1) 变换到 (x,n)(x,n) 的次数,实际上就是计算 gcd(x,n)\gcd(x,n) 时辗转相减的次数.
又由于对称性,可在 [2,n2][2,\frac{n}{2}] 中遍历所有 xx,满足 gcd(x,n)=1\gcd(x,n)=1,取辗转相减次数最小的即可.

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#define MIN(a,b) (((a)<(b))?(a):(b))
int pgcd(int a, int b)
{
int c = 0;
while(a != 1 || b != 1)
{
c++;
if(a > b) a = a - b;
else b = b - a;
}
return c;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n;
freopen("coordinate.in", "r", stdin);
freopen("coordinate.out", "w", stdout);
std::cin >> n;
if(n == 1)
{
std::cout << 0;
}
else
{
int ans = 100000000;
for(int i = n / 2; i >= 1; i--)
{
if(gcd(i, n) == 1)
{
ans = MIN(pgcd(i, n), ans);
}
}
std::cout << ans << std::endl;
}
fclose(stdin);
fclose(stdout);
}