（第五场）G max 【数论】

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

题目描述

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

输入描述:

The first line has two positive integer c,n

输出描述:

Output the maximum product of a and b.

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

case1

Input：

2 4

Output：

说明：

a=2,b=4

备注：

1<=c,n<=10^9

题目大意：

给定两个正整数 c,n，求一个数对 (a,b)，满足 1<=a,b<=n，且 gcd(a,b)=c
要求输出最大的 ab
1<=c,n<=10^9

官方题解：

首先 a 和 b 一定都是 c 的倍数，如果 c<2n，那么选 a=b=c 最优
否则选 a=(n/c)*c , b=((n/c)-1)c

大概思路：

错误解法：一开始打了个素数筛，因为想着gcd（a, b) = c，所以 a， b等于 c 乘以 1 或者某两个素数，素数的范围到 N/c；用 set 把素数存起来，然后lower_bound( ) 最接近N/c的素数，加一些判断分支。最后果断爆内存。

后来想一想，发现并不需要打素数表，其实脑洞一下有解的就是两种情况 N/c == 1，理想化的最大因子为1，所以a = b = N/c（这里wa了几次）; N/c >= 2 ,说明 a，b不等，c 分别乘以最大（N/c）和次大（（N/c）-1）。

AC code：

 #include <bits/stdc++.h>

 #define INF 0x3f3f3f3f

 #define ll long long int

 using namespace std;

 const int MAX_p = 1e8;

 ll c, N, p;

 int main()

 {

     scanf("%lld%lld", &c, &N);

     ll fmax_p = N/c, smax_p = ;

     if(fmax_p >= )

     {

         if(fmax_p == ) printf("%lld\n", fmax_p*fmax_p*c*c);

         else

         {

             smax_p = fmax_p-;

             printf("%lld\n", smax_p*fmax_p*c*c);

         }

     }

     else

     {

         printf("-1\n");

     }

     return ;

 }

巴特西