做的时候,想到相邻两个自然数互质(gcd(a,b)=1)(记得小学老师说过)
题目链接
题意:
给出c, n.找出a, b,使得gcd(a,b)=c
a$\leq$c, b$\leq$c,并且a$\times$b最大
解法:
当$n<c$时无解,输出-1
当$n\geq c$时
a和b中的约数都有c
使d=$\frac{a}{c}$, e=$\frac{b}{c}$
问题就变成
找出d, e,使得gcd(d,e)=1
d$\leq$$\lfloor \frac{n}{c} \rfloor$, e$\leq$$\lfloor \frac{n}{c} \rfloor$,d$\times$e最大
所以当$\lfloor \frac{n}{c} \rfloor$=1时,答案是$c^2$
当$\lfloor \frac{n}{c} \rfloor$$\gt$1时,答案是$c^2$$\times$($\lfloor \frac{n}{c} \rfloor$ -1)$\times$($\lfloor \frac{n}{c} \rfloor$)
代码:
1 |
|