小G的GCD
题目链接:nowcoder 217463
到主站看:https://blog.csdn.net/weixin_43346722/article/details/116243756
题目大意
问你 gcd(x,y) 用辗转相除法来求,如果限定 x,y 都小于一个值,那辗转相除法的递归最多要递归多少次。
思路
这道题给出了暴力程序,那我们就试着运行一下它,用它看看有什么规律。
然后你就从 0 开始试,你会发现答案是这样子的:(从 0 开始)
0,2,3,4,5,5,6,6,6,7,7,7,7,7,……
然后你会发现,除了 0,其它还挺有规律的,进过了一定的个数就比原来多了个 1,而且这个个数还在增加。
然后你可以看看每次的个数是多少(不算 0 了):1,1,2,3,5,……
你会发现它很像斐波那契数列,然后试着跟着算一下,发现暴力答案跟你的答案一样。
那就可以开搞了。
(其实听说可以推理出来,但是我这种弱鸡肯定是不会的啦)
代码
#include<cstdio> #include<iostream> #define ll long long using namespace std; ll n, ans, a, b, c; //根据题目给定代码进行打标找规律 //long long GCD(long long x, long long y) { // if (!y) return 1ll; // return GCD(y, x % y) + 1ll; //} // //long long maxGCD(long long n) { // long long ans = 0ll; // for (long long i = 1; i <= n; i++) // for (long long j = 1; j <= n; j++) // ans = max(ans, GCD(i, j)); // return ans; // } int main() { scanf("%lld", &n); // printf("%lld", maxGCD(n)); if (n == 0) printf("0");//先搞前几位 if (n == 1) printf("2"); if (n == 2) printf("3"); if (n == 3) printf("4"); if (n > 3) { n -= 3; ans = 4; a = 1; b = 1; c = 2; while (c < n) {//根据打标找出的规律(斐波那契)来找答案 ans++; n -= c; a = b; b = c; c = a + b; } printf("%lld", ans + (c == n)); } return 0; } //打标找规律的草稿 /* 1 2//奇数行表示第一次出现这个答案(第二个数)n 是多少(第一个数) 1//偶数行表示之间相差了多少个数 2 3 1 3 4 2 5 5 3 8 6 5 13 7 8 21 8 13 34 9 */