NUC

NUC

问题描述

XiaoMing是陪我们长大的人啊，今天他又来啦！他现在有1-n这n个数字，王老师要求他把这n个数字分成两组，每一组至少有一个数，两组数字的和的最大公约数称为“和和美美”值，XiaoMing是一个完美主义者，凡事追求尽善尽美，请问他分完组后，能得到的最大的“和和美美”值为多少？
注：int型变量的取值范围为[-231,231-1]，输入输出方式为%d；long long型变量的取值范围为[-263,263-1]，输入输出方式为%lld。

输入描述

输入一行一个整数n（2<=n<=1,000,000,000)

输出描述

输出一行一个整数表示答案。

样例输入

6

样例输出

7

题解

粘一下大佬lt的题解吧：
显然，1到n这n个数字能组成1到n*(n+1)/2内任意一个数字。
那么假设第一组数字之和是x，第二组之和是y。
那么最优情况下 x+y=n*(n+1)/2. 并且y是x的倍数。设y=kx。
那么答案应该输出x。 然后说一下怎么计算x：
n*(n+1)/2=kx。 k>=2并且 k是n*(n+1)/2的因子。
要让x最大，那么k就要最小
那么找n*(n+1)/2的最小因子，假设是k，那么答案就是(n*(n+1)/2)/k;
要算n*(n+1)/2的最小因子，n*(n+1)/2最大能达到1e18.
找n*(n+1)/2的最小因子显然会超时。
然后发现 n和n+1肯定有一个是2的倍数。
假设n是2的倍数。那么就能转化成找n/2和n+1的最小因子了。
复杂度 根号n
我看懂了，不难，比赛的时候感觉大概想到这里了，但是很遗憾，愚蠢的找因子找超时了，好菜啊，看到别人有用整除分块写过的，tql。

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {ll n;scanf("%lld",&n);ll x=n,y=n+1;if(x%2==0) {x/=2;} else {y/=2;}ll minn;if(x!=1) minn=x;else minn=y;if(y!=1) minn=min(minn,y);for(ll i=2; i*i<=x; ++i) {if(x%i==0) {minn=min(minn,i);break;}}for(ll i=2; i*i<=y; ++i) {if(y%i==0) {minn=min(minn,i);break;}}printf("%lldn",(x*y)/minn);return 0;
}