题意#

给你一个无限整数序列： $1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, \ldots$序列按以下方式构建：首先写出数字 $1$，然后写出从 $1$ 到 $2$ 的数字，然后是从 $1$ 到 $3$ 的数字，然后是从 $1$ 到 $4$ 的数字，以此类推，问你第 $n$ 个数字是什么。

题解#

按照数列的构造方式，二分或直接模拟也可。数列长度的递增速度等同于等差数列求和（$1 + 2 + 3 + \ldots + n$）

由于 $n \leq 10^{14}$，所以直接模拟可以在 $O(\sqrt n)$ 复杂度内解决问题。

题意#

给定 $a, b, l, r$。问在 $[l, r]$ 内有多少数是 $a$ 和 $b$ 的倍数， 也就是问 $[l, r]$ 内有多少数是 $lcm(a, b)$ 的倍数。

题解#

利用前缀和的思想求解即可

题意#

给定一个 $0/1$ 矩阵，你可以选择其中的一些元素，要求满足如下条件：

1. 这些元素相等。
2. 这些元素在同一行或同一列上。

问有多少种不同的选择方法。

题解#

简单组合数学。

比如对于某一行选择 $1$，如果这一行上 $1$ 的数量为 $c$，那么选择的方案数就是 $2^c - 1$（每个 $1$ 可以选和不选，但需要减掉空集的情况）。选择列和选择 $0$ 同理。

需要注意的是单个元素会被列和行重复选择，所以最终答案需要减掉所有的单个元素，即减去 $n \times m$。

代码#

#define int long long
int qpow(int a, int b, int res = 1) {
	for (; b; res = (b & 1) ? 1ll * res * a : res, a = 1ll * a * a, b >>= 1);
	return res;
}
void solve() {
	int n,m;
	cin >> n >> m;
	vector<vector<int>> b(n + 2,vector<int>(m + 2));
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> b[i][j];
		}
	}
	vector<int> r(n + 2);
	vector<int> c(m + 2);
	int ans = 0;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			r[i] += (b[i][j] == 1);
		}
		ans += qpow(2,r[i]) - 1;
		ans += qpow(2,m - r[i]) - 1;
	}
	for(int j = 1;j <= m;j ++){
		for(int i = 1;i <= n;i ++){
			c[j] += (b[i][j] == 1);
		}
		ans += qpow(2,c[j]) - 1;
		ans += qpow(2,n - c[j]) - 1;
	}
	cout << ans - n * m << '\n';
}

题意#

定义运算规则如下：

给定数组 $a$，问有多少对 $(i, j)$ 使得 $f(a_i) = f(a_j)$

题解#

首先可以发现直接递归求解 $f(a_i)$ 的复杂度在 $O(\log a_i)$，因此可以暴力求出所有 $f(a_i)$，并用一个 map 来存储 $f(x)$ 值相同的数量。

假设有 $c$ 个数的 $f(x)$ 值相同，那么对答案产生 $\frac{c \times (c - 1)}{2}$ 的贡献。

代码#

void solve() {
	int n;
	cin >> n;
	map<int,int> mp;
	function<int(int)> dfs = [&](int x){
		if(x == 0) return 0;
		if(x % 2 == 0) return dfs(x / 2);
		return dfs(x / 2) + 1;
	};
	for(int i = 1;i <= n;i ++){
		int x;
		cin >> x;
		mp[dfs(x)] ++;
	}
	ll ans = 0;
	for(auto [u,v] : mp){
		ans += 1ll * v * (v - 1) / 2;
	}
	cout << ans << '\n';
}

题意#

给你一个长为 $n$ 的数组 $a$，判断这个数组是否能通过特定的 $n$，$m$，$c$，$s$ 四个数通过以下方式生成，如果能，最大化 $m$ 的值。

• $a_1 = s \mod m$
• 对于所有 $1 \leq i \leq n$ 的 $i$，$a_i = (a_{i-1} + c) \mod m$

题解#

首先单独处理 $c = 0$ 的情况。为此，检查对于 $1 \leq i \leq n - 1$ 中的每个 $i$，是否存在等式 $a_i = a_{i+1}$（或者换句话说，所有数字都相同）。如果这是真的，那么模可以任意大。否则，如果 $a_i = a_{i+1}$ 对至少一个 $i$ 成立，则 $c$ 必须等于零，但我们已经存在不相等的数。所以答案是 $-1$。

那么，现在 $c \neq 0$，没有两个连续的数字相等。

可以发现，$x+c \mod m$ 是 $x+c$ 或 $x-(m - c)$。 因此，所有正差（连续数字对之间）必须相同，所有负差也必须相同。否则，答案为 $-1$。

如果没有正差异（或者类似地，如果没有负差异），则模可以任意大。 否则，模必须等于它们的和 $c + (m - c) = m$。

找到 $m$ 和 $c$ 之后，只需要检查它们是否真的生成了正确的序列即可。

代码#

int a[maxn];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	if(n == 1){
		cout << 0 << '\n';
		return;
	}
	bool f1 = 0,f2 = 0;
	for(int i = 1;i < n;i ++){
		f1 |= (a[i] == a[i + 1]);
		f2 |= (a[i] != a[i + 1]);
	}
	set<int> d1,d2;
	if(f1 && f2){
		cout << -1 << '\n';
		return;
	}
	if(f1 && !f2){
		cout << 0 << '\n';
		return;
	}
	for(int i = 1;i < n;i ++){
		if(a[i + 1] - a[i] > 0){
			d1.insert(a[i + 1] - a[i]);
		}else{
			d2.insert(a[i] - a[i + 1]);
		}
	}
	if(d2.empty()){
		if(d1.size() == 1){
			cout << 0 << '\n';
		}else{
			cout << -1 << '\n';
		}
		return;
	}
	if(d1.empty()){
		if(d2.size() == 1){
			cout << 0 << '\n';
		}else cout << -1 << '\n';
		return;
	}
	if(d1.size() == 1 && d2.size() == 1){
		int c = *d1.begin();
		int m = c + *d2.begin();
		int now = a[1];
		if(now >= m){
			cout << -1 << '\n';
			return;
		}
		for(int i = 2;i <= n;i ++){
			now = (now + c) % m;
			if(now != a[i]){
				cout << -1 << '\n';
				return;
			}
		}
		cout << m << ' ' << c << '\n';
	}else{
		cout << -1 << '\n';
	}
}

题意#

求有多少对 $(a, b)$ 满足 $\lfloor{\frac{a}{b}} \rfloor = a \mod b$ $(1 \leq a \leq x, 1 \leq b \leq y)$

题解#

容易发现满足条件的 $a, b$ 在形式上满足 $a = k \times b + k$ $(k < b)$

由于 $k < b$，所以 $k \times b + k$ 的大小在 $O(k^2)$，因此可以 $O(\sqrt{x})$ 枚举 $k$，并计算有多少 $b$ 满足 $k < b \leq y$ 且 $k \times b + k \leq x$。这一过程可以 $O(1)$ 计算，也可以靠二分解决。前者的复杂度为 $O(T \times \sqrt{x})$

代码#

void solve() {
	ll x,y;
	cin >> x >> y;
	ll ans = 0;
	for(int k = 1;k * (k + 1) + k <= x;k ++){
		ans += max(0ll,min(y,(x - k) / k) - k);
	}
	cout << ans << '\n';
}