国内视差网站百度广告投放平台官网
今天早上做了算法题，其中一道如下所示:
你需要在1s内算出答案。
题目如下：
给出正整数n，求a+b的最大值
其中a，b为正整数，a<=n且b<=n且gcd(a,b)=1
ps：gcd是最大公约数
>>>>对于50%的数据，n < 1000
>>>>对于100%的数据，n < 1亿
做的过程中也没由考虑时间、大整数这些，先把代码贴下来记住吧。
#include <iostream>#include<windows.h> using namespace std;int main(){DWORD dwStart = GetTickCount(); int n;cin >> n;int flag = 0;int max = 0;for (int a = 1; a <= n; a+=2) //因为两个偶数的最大公约数一定不是1，所以这里每次循环后a+=2, b+=1。{for (int b = 1; b <= n; ++b){for (int k = 2; k <= min(a, b); ++k) //求最大公约数{if (a % k == 0 && b % k == 0){flag = 1;break;}}if (flag == 0 && max < a+b){max = a+b;}}}cout << max << endl;DWORD dwTime = GetTickCount() - dwStart; cout << dwTime << endl;return 0;}
先不考虑代码，梳理一下知识点：
一、求最大公约数、最小公倍数
1、最小公倍数
如有两个数x、y，则x * y = 最大公约数 * 最小公倍数
2、最大公约数
①辗转相除法：
/*非递归解法*/
int gcd(int x, int y) //最大公约数：greatest common divisor
{int z = y;while (x % y != 0){z = x%y;x = y;y = z;}return z;
}/*递归解法*/
int gcd(int a, int b)
{return b ? gcd(b, a%b) : a;
}
②辗转相减法：
int gcd(int a, int b)
{while (a != b){if (a > b){a = a-b;}else{b = b-a;}}return a;
}
③穷举法：
int gcd(int x, int y)
{int temp = min(x, y);while (!(x%temp == 0 && y%temp == 0)){--temp;}return temp;
}
二、测试时间
这大概是我一直不明白的问题，每次查来查去，每次也理不清什么。自测的结果总是让人感觉怪怪的(感觉时间数字和单位不一致)。这次也贴一个今天早上找的一篇博客的链接：https://blog.csdn.net/tianshuai1111/article/details/7544431
三、大整数
具体会有大整数的加减乘除各种运算，今天早上的练习很多都是这方面的，要梳理强化！大整数应该是一个考点的方向的，先把加减乘除最基本的弄好！
也是先贴一个博客的链接：https://www.cnblogs.com/FZfangzheng/p/7700699.html
之前看书，有大整数的乘法，用分治法实现，这周也要尽量补上！
Ps：这次做题，关于图、网的还是就那样空了，也没思考。要先把书上的图这一章的好好消化一下，之后重点练习！
And，纪念一下第一次用Markdown写博客，哈哈哈太好玩了,确实很方便！~