wls 有一个整数 n,他想将 1 − n 这 n 个数字分成两组,每一组至少有一个数,并且使得两组数字的和的最大公约数最大,请输出最大的最大公约数。
Input
输入一行一个整数 n。
2 ≤ n ≤ 1, 000, 000, 000
Output
输出一行一个整数表示答案。
Sample Input
6
Sample Output
7
思路:
我们求1到n的sum和为sum,
分成的两组的sum和分别是sum1和sum2,
那么根据题意我们知道 sum1+sum2=sum
所求的答案就是 gcd(sum1,sum2) 中最大的,我们设为ans
根据gcd性质我们知道 gcd(sum1,sum2)=gcd(sum1,sum)=gcd(sum2,sum)
因为 gcd(x,y)=gcd(x,x+y)
那么我们可以得出等式 :
sum1/ans+sum2/ans = sum/ans
显然ans是sum的一个因子,我们想得到的是最大的ans,即sum最大的因子。
如何找到一个数最大的因子呢?我们只需要暴力枚举找到sum最小的因子x ,sum/x=ans。
细节见代码:
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#include <vector>#include <iomanip>#define ALL(x) (x).begin(), (x).end()#define sz(a) int(a.size())#define all(a) a.begin(), a.end()#define rep(i,x,n) for(int i=x;i<n;i++)#define repd(i,x,n) for(int i=x;i<=n;i++)#define pii pair<int,int>#define pll pair<long long ,long long>#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define eps 1e-6#define gg(x) getInt(&x)#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endlusing namespace std;typedef long long ll;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}ll lcm(ll a,ll b){return a/gcd(a,b)*b;}ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}inline void getInt(int* p);const int maxn=1000010;const int inf=0x3f3f3f3f;/*** TEMPLATE CODE * * STARTS HERE ***/int main(){//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);ll n;cin>>n;if(n==2){return puts("1");}else{ll sum=(n+1ll)*n/2ll;for(ll i=2ll;;++i){if(sum%i==0){cout<<sum/i<<endl;break;}}}return 0;}inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}}}