admin 管理员组文章数量: 887021
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("%lld\n",(x*y)/minn);return 0;
}
本文标签: nuc
版权声明:本文标题:NUC 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1730872751h1398555.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论