2018牛客多校05 G max(数学，规律)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://www.nowcoder.com/acm/contest/143/G

给定c、n，求两个整数a、b，使得$gcd(a,b)=c, 1≤a,b≤n$

很容易发现只需要选择最接近n的c的倍数数、以及次接近n的c的倍数乘积就是最大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
 
using LL = long long;
LL c, n;
 
signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%lld%lld",&c,&n)) {
    if(c > n) {
      printf("-1\n");
      continue;
    }
    if(c == 1) {
      if(n == 1) printf("1\n");
      else printf("%lld\n", n*(n-1));
      continue;
    }
    bool flag = 1;
    if(n == c) {
      printf("%lld\n", c * c);
      continue;
    }
    if(n % c == 0) printf("%lld\n", n*(n-c));
    else {
      LL t = n / c * c;
      if(t == c) printf("%lld\n", t*t);
      else printf("%lld\n", t*(t-c));
    }
  }
  return 0;
}