牛客第五场 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

示例1

输入

复制

2 4

输出

复制

8

说明

a=2,b=4

备注:

1<=c,n<=10^9

题意：给你两个数c，n，问你1-n之间最大的两个最大公约数是c的数的乘积
分析：分三种情况考虑：
　　　　当c大于n时，n以内没有能够整除c的数，明显答案是-1，
　　　　当n整除c的结果为1时，明显n以内的c可以整除c，此时答案是c*c
　　　　因为要找最大公约数是c的两个数，所以这些数肯定要能整除c，考虑先除以c，则剩下的数都是1-n范围内能整除c的，由于这两个数的最大公约数必须是c，所以他们必须互质。
　　　　到此我们要找的就是除以c后最大的两个互质数，因为n与n-1互质，所以此时的答案就是除以n后最大的数和比他小于1的数的乘积
AC代码：

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll c, n;
    while( cin >> c >> n ) {
        if( n/c < 1 ) {
            cout << -1 << endl;
        } else if( n/c == 1 ) {
            cout << c*c << endl;
        } else {
            cout << (n/c-1)*(n/c)*c*c << endl;
        }
    }
    return 0;
}