HDU 4627

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

There are many unsolvable problem in the world.It could be about one or about zero.But this time it is about bigger number.
Given an integer n(2 <= n <= 10 ⁹).We should find a pair of positive integer a, b so that a + b = n and [a, b] is as large as possible. [a, b] denote the least common multiplier of a, b.

Input

The first line contains integer T(1<= T<= 10000),denote the number of the test cases.
For each test cases,the first line contains an integer n.

Output

For each test cases, print the maximum [a,b] in a line.

Sample Input

3
2
3
4

Sample Output

1
2
3

此题的话，因为一个数n由两个正整数a+b得来，所以可以先确定a和b的范围，是从1到n/2

因为从n/2+1到n，是和前半部分重复，不用计算

然后，就用辗转相除法，a,b互质，输出最大的 LCM(a, b），即a，b的最小公倍数最大。

注意：这种算法易懂，但是很容易超时，自己做的时候就是

#include <stdio.h>

int main()

{

    int a,b,c;

    int max,min,t1,t2;

    int i,n,T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        max=;

        for(i=; i<=n/; i++)

        {

            a=i;

            b=n-i;

            a>b?t1=a:t1=b;

            t2=n-t1;

            while(t2)

            {

                c=t1%t2;

                t1=t2;

                t2=c;

            }

            min=a*b/t1;

            if(min>max)

                max=min;

        }

        printf("%d\n",max);

    }

    return ;

}

另外还有一种，这是一种奇偶求法，很简单巧妙，经某ACM大神指点得知

#include <stdio.h>

int main()

{

    int n,T;

    long long max;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        max=;

        if (n==) printf("1\n");

        else

        {

            if (n%==)

            {

                max=n/;

                if (max%==) max=(max+)*(max-);

                else max=(max+)*(max-);

            }

            else

            {

                max=n/;

                max=max*(max+);

            }

            printf("%I64d\n",max);

        }

    }

    return ;

}

巴特西

HDU 4627（最小公倍数最大问题）

HDU 4627

最新文章

热门文章