HDU 4627（最小公倍數最大問題），hdu4627

                       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=0;
for(i=1;i<=n/2;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 0;
} 

 

另外還有一種，這是一種奇偶求法，很簡單巧妙，經某ACM大神指點得知

#include <stdio.h>

int main()
{
int n,T;
long long max;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
max=0;
if (n==2) printf("1\n");
else
{
if (n%2==0)
{
max=n/2;
if (max%2==0) max=(max+1)*(max-1);
else max=(max+2)*(max-2);
}
else
{
max=n/2;
max=max*(max+1);
}
printf("%I64d\n",max);
}
}
return 0;
}