Ilumina 题解

30 分解法

$a, c \le 10$ 的部分分。

已知 $b = \left \lfloor \dfrac{a}{n} \right \rfloor$，$c = \left \lfloor \dfrac{b}{m} \right \rfloor$，并且 $a$ 和 $c$ 的值已经给定。我们将 $b = \left \lfloor \dfrac{a}{n} \right \rfloor$ 代入 $c = \left \lfloor \dfrac{b}{m} \right \rfloor$ 中，得到下列式子。

$$c = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor $$

因为 $n, m, a, b, c$ 均为正整数，并且 $n$ 和 $m$ 在 $b = \left \lfloor \dfrac{a}{n} \right \rfloor$ 和 $c = \left \lfloor \dfrac{b}{m} \right \rfloor$ 中均为分母，因此只有当 $n \le a$ 且 $m \le b$ 时，$b$ 和 $c$ 才为正整数。

枚举 $[1, a]$ 中的整数 $n$ 和 $\left[1, \left \lfloor \dfrac{a}{n} \right \rfloor \right]$ 中的整数 $m$，并判断是否有满足 $\left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor = c$ 的 $n$ 和 $m$ 即可。

---

60 分解法

$a, c \le 10^3$ 的部分分。

使用 $\{ x \}$ 表示 $x$ 的小数部分，显然 $\{ x \} <1$，因此下列式子中 $\left \{ \dfrac{a}{n} \right \}$ 的值不可能改变式子的取值。

$$\left \lfloor \dfrac{a}{nm} \right \rfloor = \left \lfloor \dfrac{\dfrac{a}{n}}{m} \right \rfloor = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor + \left \{ \dfrac{a}{n} \right \} }{m} \right \rfloor = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor $$

所以 $c = \left \lfloor \dfrac{a}{nm} \right \rfloor$。因为 $n$ 和 $m$ 可以为任意正整数，我们令 $n = 1$，此时 $b = a$，$c = \left \lfloor \dfrac{a}{m} \right \rfloor$。枚举 $m$ 即可。

---

80 分解法

$a, c \le 10^3$ 和特殊性质的部分分。

对于特殊性质，因为合法的 $b$ 始终存在，可以发现有如下等式成立。

$$c = \left \lfloor \dfrac{\left \lfloor \dfrac{a}{n} \right \rfloor}{m} \right \rfloor = \left \lfloor \dfrac{b}{m} \right \rfloor $$

$m$ 可以为任意正整数，因此我们令 $m = 1$，即可得到 $b = c$。直接输出 $c$ 的值即可。

---

正解

由 60 分解法可以发现，问题转化成了判断是否存在正整数 $m$ 使得 $c = \left \lfloor \dfrac{a}{m} \right \rfloor$。

如果存在这样的 $m$，由于构造中 $n=1$，直接输出 $a$ 即可。

$$\left \lfloor \dfrac{a}{\left \lfloor \dfrac{a}{c} \right \rfloor} \right \rfloor \ge \left \lfloor \dfrac{a}{\dfrac{a}{c}} \right \rfloor = \left \lfloor c \right \rfloor = c = \left \lfloor \dfrac{a}{m} \right \rfloor $$

存在合法的 $m$ 当且仅当存在区间 $[l,r]$ 满足 $l \leq r$ 且对于 $i \in [l,r] \cap \mathbb{Z}$ 有 $\left \lfloor \dfrac{a}{i} \right \rfloor =c$。

很显然，最大的满足条件的 $i$（使用 $i_0$ 表示）满足 $i_0 \times c \leq a$ 且 $(i_0+1) \times c > a$，容易得到 $i_0 = \left \lfloor \dfrac{a}{c} \right \rfloor$，计算 $i_0$ 的值并且检验 $\left \lfloor \dfrac{a}{i_0} \right \rfloor$ 是否等于 $c$ 即可判断是否存在合法的 $m$。

单组数据时间复杂度 $O(1)$。

#include <iostream>
using namespace std;
using ll = long long;

int t;
ll a, c;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        cin >> a >> c;
        if (a < c) cout << "-1\n";
        else cout << (a / (a / c) == c ? a : -1) << '\n';
    } return 0;
}

可能的其他解法

由 60 分解法可以得到 $m$ 具有单调性，因此可以对 $m$ 进行二分查找。单组数据时间复杂度 $O(\log n)$。

解题思路：

分类讨论题，分类如下：

• 当 $a < c$ 时，由于 $b,n,m$ 为正整数，所以无法得到合法的 $b$。
• 当 $a \div (a \div c) \ne c$ 时，由于 $a$ 无法通过连除得到 $c$，同样无法得到合法的 $b$。
• 其他情况，最简单的方法就是把 $m$ 设为一，得 $b = c$。

CODE:

#include <iostream>
using namespace std;
long long t, a, c;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> a >> c;
        if (a < c)
        {
            cout << "-1\n";
            continue;
        }
        if (a / (a / c) != c)
            cout << "-1\n";
        else
            cout << c << '\n';
    }
    return 0;
}

Code

题解分析

问题描述

给定五个正整数 $n$, $m$, $a$, $b$, $c$，其中 $b = \lfloor \frac{n}{a} \rfloor$ 且 $c = \lfloor \frac{m}{b} \rfloor$。已知 $a$ 和 $c$ 的值，求出一个合法的 $b$ 的值，或者报告不存在合法的 $b$ 的值。

解题思路

根据题目描述，我们有以下两个等式：

$$b = \lfloor \frac{n}{a} \rfloor$$ $$c = \lfloor \frac{m}{b} \rfloor$$

由第一个等式，我们可以推断出 $a \cdot b \leq n$。由第二个等式，我们可以推断出 $b \cdot c \geq m$。结合这两个不等式，我们可以得出 $b$ 应该满足 $a \leq b \leq c$。

解决方案

我们可以直接检查 $c$ 是否满足条件。如果 $c$ 满足 $a \leq c \leq c$，那么 $c$ 就是一个合法的 $b$ 值。否则，不存在合法的 $b$ 值。

代码实现

以下是使用 C++ 实现的代码片段：

#include <iostream>
using namespace std; 
 
int main() {
    int t; 
    cin >> t; 
    while(t--) { 
        long long a, c;
        cin >> a >> c; 
        if(a <= c && a / (a / c) == c) cout << c << endl; 
        else cout << -1 << endl; 
    }
    return 0; 
} 

时间复杂度分析:

这个解决方案的时间复杂度是 ，因为它只需要常数时间来处理每个测试用例。这使得它非常适合处理大量的测试数据。

J1B 题解

第三篇题解。

显然，当 $a<c$ 时一定无解。再判断 $\lfloor\frac a{\lfloor\frac ac\rfloor}\rfloor=c$ 是否成立，若成立一定有解 $b=c$，否则无解，输出 $-1$。

代码：

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long a,c;
        cin>>a>>c;
        if(a>=c&&a/(a/c)==c)cout<<c<<endl;
        else cout<<"-1\n";
    }
    return 0;
}

看似很难，实则是一道水题。

由 $b=\left\lfloor \frac{a}{n} \right\rfloor , c=\left\lfloor \frac{b}{m} \right\rfloor$，得$ c=\left\lfloor \frac{\left\lfloor \frac{a}{n} \right\rfloor}{m} \right\rfloor=\left\lfloor \frac{a}{nm} \right\rfloor$，

所以 $\left\lfloor \frac{a}{c} \right\rfloor\ge1$。

再考虑其他无解：

如果 $\left\lfloor \frac{a}{\left\lfloor \frac{a}{c} \right\rfloor} \right\rfloor\gt c$，则找不到 $nm$。

证明：略

接下来考虑如何求解。

最简单的解是 $b=c$。(当 $n=nm,m=1$ 时，$b$ 可以 $=c$)

故代码如下：

#include<bits/stdc++.h>
using namespace std;
//a/n/m=c
signed main(){
	long long t,a,b,c;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&a,&c);
		if(a/c<1||a/(a/c)<=c)printf("-1\n");
		else printf("%lld\n",c);
	}
} 

阿达房地产

阿达房地产

GCC

gcc main.cpp

解题方法

就算一个

$x + y = 114514$

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(ye \s 14514 n)$

空间复杂度:

问啊大出血是 添加空间复杂度, 示例： $O(log n)$

Code

C啊带带我

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long a,c;
        cin>>a>>c;
        if(a>=c&&a/(a/c)==c)cout<<c<<endl;
        else cout<<"-1\n";
    }
    return 0;
}

这是一道简单题。

我们不妨设 $n = 1$，因为这样可以让 $b$ 尽量大，从而找出一个合法的解。

那么问题转换为：是否存在一个 $m$ 满足 $c = \lfloor \frac{a}{m} \rfloor$。

我们可以采用二分查找的方法，在 $(\lfloor \frac{a}{c + 1} \rfloor, \lfloor \frac{a}{c} \rfloor]$ 这个区间进行查找即可。

单次询问时间复杂度 $O(\log n)$。

参考代码如下：

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define ll long long
#define writes(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n');
static char buf[100000], * pa(buf), * pb(buf);
int st[114], top;
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void debug(auto st, auto ed, bool endline) {
	for (auto it = st; it != ed; ++it) {
		cout << *it << " ";
	}
	if (endline) cout << '\n';
}
template <typename T> void read(T& x) {
	T t = 0, sgn = 1;
	char ch = gc;
	while (!isdigit(ch)) {
		if (ch == '-') sgn = -sgn;
		ch = gc;
	}
	while (isdigit(ch)) {
		t = (t << 3) + (t << 1) + (ch ^ 48);
		ch = gc;
	}
	x = sgn * t;
}
template <typename T, typename ...Args> void read(T& tmp, Args &...tmps) {
	read(tmp); read(tmps...);
}
template <typename T> void write(T x) {
	if (x < 0) putchar('-'), x = -x;
	top = 0;
	while (x) {
		st[++top] = x % 10;
		x /= 10;
	}
	do {
		putchar(st[top--] + '0');
	} while (top > 0);
}
template <typename T, typename ...Args> void write(T& tmp, Args &...tmps) {
	writes(tmp);
	writes(tmps...);
}
template <typename T> T rand(T l, T r) {
	return rnd() % (r - l + 1) + l;
}
int main() {
	// cin.tie(0)->sync_with_stdio(0);
	// cout.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		ll a, c;
		read(a, c);
		ll l = a / (c + 1) + 1, r = a / c;
		bool ok = 0;
		while (l <= r) {
			ll mid = l + r >> 1;
			if (a / mid == c) {
				ok = 1;
				writeln(a);
				break;
			}
			if (a / mid > c) {
				l = mid + 1;
			}
			else r = mid - 1;
		}
		if (!ok) puts("-1");
	}
}

标题

思路

解题方法

114514

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code