HDU 4627(最小公倍数最大问题)

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 9).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 ;
}
上一篇:模拟器配置使用Fildder进行抓包,包含Https+证书


下一篇:flex-grow