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

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\left]\right)$gcd(i,j)=c(i,j∈[1,n])，求 $max(i\ast j)$max(i∗j)。

$i=k1\times c,j=k2\times c$i=k1×c,j=k2×c， $\because gcd(i,j)=c\therefore k1$∵gcd(i,j)=c∴k1和 $k2$k2互质，找到最大的 $k1,k2$k1,k2即可。

$max\left(k\right)=\lfloor \frac{n}{c}\rfloor$max(k)=⌊cn​⌋，而 $k-1$k−1一定与 $k$k互质， $\therefore k1=\lfloor \frac{n}{c}\rfloor ,k2=\lfloor \frac{n}{c}\rfloor -1$∴k1=⌊cn​⌋,k2=⌊cn​⌋−1

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

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout << #x << "=" << x << endl;
#define ArrayDebug(x,i) cout << #x << "[" << i << "]=" << x[i] << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
	char c;
	int sgn;
	if (c = getchar(), c == EOF) {
		return 0;
	}
	while (c != '-' && (c < '0' || c > '9')) {
		c = getchar();
	}
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0' && c <= '9') {
		ret = ret * 10 + (c - '0');
	}
	ret *= sgn;
	return 1;
}
template <class T>
inline void out(T x) {
	if (x > 9) {
		out(x / 10);
	}
	putchar(x % 10 + '0');
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ll c, n;
	read(c); read(n);
	if (c > n) {
		printf("-1\n");
	}
	else if (n / c == 1) {
		printf("%lld\n", c * c);
	}
	else {
		printf("%lld\n", c * c * (n / c) * (n / c - 1));
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}