20250723 河南萌新2

M

签到。

勾股定理列出来然后观察即可，最后答案是 $\frac{\pi x^2}{8}$

K

签到，直接输出那个玩意就行。

I

题意等价于求二分答案的时间复杂度，如果n是2的次幂，答案就是__lg(n)；如果不是的话，就要多搜索一次。

如何高效判断 n 是否是 2 的次幂？ 可以采用

if ((n & (n - 1)) != 0) ans++;

由于 & 的优先级较低，这里的括号应当是一个都不能少的，可以自行尝试。

D

建图之后dfs。

dfs 的时候要注意如何高效识别 当前的节点 cur 是哪条路过来的，可以考虑建立一个前驱数组，也可以直接在 dfs 的参数上加上。

最后查询二进制 1 的数量，可以用 __builtin_popcount 做到 o1 查询。

void solve()
{
    int n, q;
    cin >> n >> q;
 
    vector<int> a(n + 1);
    vector<vector<int>> adj(n + 1, vector<int>());
    vector<int> ans(n + 1);
 
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
 
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
 
    vector<int> pre(n + 1, 0); // 记录前驱节点
 
    ans[1] = a[1];
    function<void(int)> dfs = [&](int cur)
    {
        for (auto nxt : adj[cur])
        {
            if (nxt == pre[cur]) 
            // 如果 nxt 是 cur 的前驱节点 说明绕回去了，不选
            {
                continue;
            }
 
            pre[nxt] = cur;
            ans[nxt] = a[nxt] & ans[cur];
            dfs(nxt);
        }
    };
    dfs(1);
    map<int, int> anss;
    for (int i = 1; i <= n; i++)
    {
        auto cur = __builtin_popcount(ans[i]);
        anss[cur]++;
    }
 
    while (q--)
    {
        int op;
        cin >> op;
        cout << anss[op] << endl;
    }
}

A

我们要计算 1~n 的 所有 约数和。

什么是约数呢，比方说 n = 6 那么它的约数就有 1, 2, 3, 6 。

可以看出来，约数指的是能整除n的数字。

那么 对于数字2，从1到6到底有多少数字能被2整除呢？

能被2整除的数字 一定可以写成2k的形式，那也就是找1到6有多少个2k 问题转化为计算k的最大值

显然在这个例子里，$k=\frac{n}{2}=3$ 。

因此 我们得到一个小结论，计算 1 ~ n 有多少个数字整除 i 只需要计算 $\lfloor \frac{n}{i}\rfloor$ 即可。

那么这道题我们就成功的转化为

int ans = 0;
for (int i = 1; i <= n; i++) ans += n / i;

但是 $n\le 2^{31}$ 这样做是很有可能超时的，因此我们有必要学习数论分块。

---

数论分块，也称整除分块，是一种 用来解决形如 ${\sum }_{i=1}^{n}f(i)\lfloor \frac{n}{i}\rfloor$ 的问题 的优化技巧。

观察一个重要性质：对于固定的 n , $\lfloor \frac{n}{i}\rfloor$ 的取值是有限的。

关键定理 ：对于正整数 n ，$\lfloor \frac{n}{i}\rfloor$ 最多只有 $2\sqrt{n}$​ 种不同的取值。

在一个 $\lfloor \frac{n}{i}\rfloor$ 相等 的区间$R$内，我们显然有 $\forall i,j\in R,\frac{n}{i}=\frac{n}{j}$

那么我们如果已经知道一个区间的左端点是 $l$ 也就可以通过这个式子 计算出 区间的右端点 $r=\frac{n}{\frac{n}{l}}$

特别注意的是，这里的除法都是整除，不要觉得好看就轻易化简。

在计算出区间左右端点之后，我们累计答案，然后更新左端点，再次计算即可。

void solve()
{
	int n;
	cin >> n;
	int ans = 0;
	int l = 1, r;
	while (l <= n)
	{
		r = n / (n / l);
		auto tot = r - l + 1; // 有多少个数字 满足 n/i 不变
		ans += tot * (n / l);
		l = r + 1;
	}
	cout << ans;
}

或者我们也可以精简一点，写成

void solve()
{
	int n;
	cin >> n;
	int ans = 0;
 
	for (int l = 1, r; l <= n; l = r + 1)
	{
		r = n / (n / l);
		ans += (r - l + 1) * (n / l);
	}
	cout << ans;
}

问题得到解决。