wls 有一個(gè)整數(shù) n，他想將 1 ? n 這 n 個(gè)數(shù)字分成兩組，每一組至少有一個(gè)數(shù)，并且使得兩組數(shù)字的和的最大公約數(shù)最大，請輸出最大的最大公約數(shù)。
Input
輸入一行一個(gè)整數(shù) n。
2 ≤ n ≤ 1, 000, 000, 000
Output
輸出一行一個(gè)整數(shù)表示答案。
Sample Input
6
Sample Output
7

思路：

我們求1到n的sum和為sum，

分成的兩組的sum和分別是sum1和sum2，

那么根據(jù)題意我們知道 sum1+sum2=sum

所求的答案就是 gcd(sum1,sum2) 中最大的，我們設(shè)為ans

根據(jù)gcd性質(zhì)我們知道 gcd(sum1,sum2)=gcd(sum1,sum)=gcd(sum2,sum)

因?yàn)?gcd(x,y)=gcd(x,x+y)

那么我們可以得出等式 ：

sum1/ans+sum2/ans = sum/ans

顯然ans是sum的一個(gè)因子，我們想得到的是最大的ans，即sum最大的因子。

如何找到一個(gè)數(shù)最大的因子呢？我們只需要暴力枚舉找到sum最小的因子x ，sum/x=ans。

細(xì)節(jié)見代碼：

#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)<<"]"<<endl using 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';}} }

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11291976.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Gcd HDU - 6545 （基础数论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。