[思维]hdu-6545-Gcd

发布于 2019-07-17  978 次阅读


http://acm.hdu.edu.cn/showproblem.php?pid=6545

解题思路:
这个题一开始卡了好一会。。。将1-n这n个数分成两组 每组之和的最大公约数
求这个最大的最大公约数
sum1/max+sum2/max=sum/max
这样想 我们并不需要求出sum1 sum2具体的值 我们只需要求sum是多少 max是sum最大的质因子
sum/max=min->sum/min=max
所以我们从2开始求min 对应的就可以找到max是多少了!

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<ctime>
#include<stack>
#include<map>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;

int main() {
	int n;
	cin >> n;
	ll sum = (n + 1) * n / 2;
	if (n == 2) {
		cout << 1 << endl;
		return 0;
	}
	for (int i = 2; i <= n; i++) {
		if (sum % i == 0) {
			cout << sum / i << endl;
			break;
		}
	}
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。