代码源每日一题 2022-5-9

数学 - 题目 - Daimayuan Online Judge

给定整数 n，胖教授想将1∼n这nn个数字分成两组，每一组至少有一个数，并且使得两组数字的和的最大公约数最大，请输出最大的最大公约数。

输入格式：

一行输入一个n。

输出格式：

输出一个最大的公约数。

数据：

对于20%的数据，保证n≤100。

对于100的数据，保证n≤1e9。

输入样例：

6

输出样例

7 

好了，题目已经看完了，然后就是解题了。

1：我们先来转化题意因为题目是1~n分成俩组数据，那1~ 1 + 2 + 3 +....+n之间的任何一个数都可能被分成一组，然后其余的数就是在另外一组。

也就是说我们先设sum为1~n的和。 分成俩组就理解成把sum分解成x,sum-x，这俩个数，x可以是1~sum的任何一个数。然后让我们求x , sum - x的最大的公约数的值。那再转化成一个更容易理解的东西，也就是说最少把sum整分成几份。

2：题目意思转换完成之后，题目就变得十分简单，那就是说看sum最小可以整除几（i），然后输出sum / i 就可以了，我们知道i 只可能在 2 ~  sqrt(sum) ，所以我们的搜索范围最大到sqrt(sum)，但是我们这里sum会有很大，很明显会超时，那我们怎么办呢，这里我们又联想到sum的公式sum= n * ( n + 1 ) / 2, 我们知道sum又俩部分组成，那我们只需要分别求出这俩部分的可以整除的最小值然后再进行比较，取出那个最小的就好了，这个时候每一个i都子啊 2~sqrt(n) 之间，我们就避免了超时的问题。

3：还需注意n= 2 这一特殊情况。 今天的题目不难，但是题解却改了几次，因为一开始就是直接搜索2 ~ sqrt（sum）然后搜索到之后退出，感觉就不会出现问题，但是没有搞懂是为什么，后来觉得可能是数据的问题，或者别的一些什么原因，反正我自己无法证明我的正确性，然后又重新写了一份。

第一次的代码

#include
using namespace std;
int main()
{
    long long n;
    cin >> n ;
    long long sum;
    sum =(n + 1) * n / 2;
    for(long long i = 2 ; i * i <= sum ; i++)
    {
        if(sum % i == 0)
        {printf("%lld",sum/i);break;}
    }
    return 0;
}

  我给出的题解的代码：

#include
using namespace std;
int main()
{
    long long n;
    cin >> n ;
    if( n == 2)
    {
        cout << 1 << endl;
        return 0;
    }
    long long  x , y;
    if(n % 2) x = n , y = ( n + 1 )  / 2;
    else x = n / 2 , y = n + 1;
    long long sum =  n * (n + 1) / 2;
    for(int i = 2 ;  i <= x / i ; i ++ )
    {
        if(x % i == 0)
        {
            x = i ;
            break;
        }
    }
    for(int i = 2 ; i<= y / i ; i ++)
    {
        if(y % i == 0)
        {
            y = i ;
            break;
        }
    }
    cout << sum / min(x , y) << endl;
    return 0;
}