牛客网暑期ACM多校训练营(第五场) G max

  • 2018-08-08
  • 9
  • 0

Description:

Give two positive integer c, n. You need to find a pair of integer (a,b) satisfy 1<=a,b<=n and the greatest common division of a and b is c.And you need to maximize the product of a and b

Input:

The first line has two positive integer c,n

Output:

Output the maximum product of a and b.

If there are no such a and b, just output -1

Sample Input:

2 4

Sample Output:

8

Hint:

1<=c,n<=10^9

题目链接

gcd(i,j)=c(i,j\in[1,n]),求max(i*j)

i=k1\times c,j=k2\times c\because gcd(i,j)=c\therefore k1k2互质,找到最大的k1,k2即可。

max(k)=\lfloor\frac{n}{c}\rfloor,而k-1一定与k互质,\therefore k1=\lfloor\frac{n}{c}\rfloor,k2=\lfloor\frac{n}{c}\rfloor-1

注意特判\lfloor\frac{n}{c}\rfloor=1以及无解的情况

AC代码:

评论

还没有任何评论,你来说两句吧