挖土机 CSP-J 模拟赛 ~ 第十场

打草惊蛇

其实看看数据范围，就是个暴力枚举。

出题时想的是凑数让后期选手写筛写 lcm 浪费点时间。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[25];
int main()
{
	freopen("da.in", "r", stdin);
	freopen("da.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int ans = 0;
	for (int i = 1; i <= m; i++)
	{
		int now = 0;
		for (int j = 1; j <= n; j++)
			if (i % a[j] == 0)
				now++;
		ans = max(ans, now);
	}
	cout << ans;
	return 0;
}

借尸还魂

首先 $a+b+c+d=a+b+(a+b)+(b+(a+b))=3a+4b$ 这个应该都很好推。

然后，应该很好想到 $O(n^2)$ 暴力枚举的代码。

// O(n^2) 暴力枚举
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a, b;
signed main()
{
	freopen("jie.in", "r", stdin);
	freopen("jie.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	a = 1, b = 2;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (abs(n - 3 * i - 4 * j) < abs(n - 3 * a - 4 * b))
				a = i, b = j;
	cout << a << " " << b << " " << a + b << " " << a + 2 * b << "\n";
	return 0;
}

接下来有两种常见满分路线

• 一种是修改上面的代码套一层 for 循环枚举 $1\sim 100$ 的结果，容易发现 $a$ 必然是 $1\sim 4$ 中的一个，此时就可以写出来 $O(n)$ 的代码了，然后进一步如果能推出 $b$ 是大于 $a$ 且最接近 $\frac{n-3a}{4}$ 的数，就能 $O(1)$ 做了
• 还有一种是先推出 $b$ 是大于 $a$ 且最接近 $\frac{n-3a}{4}$ 的数，可以二分或者数学方法算出，这就是 $O(n\log n)$ 或 $O(n)$。然后进一步数学推式子，发现 $a>4$ 时，$3a+4b=3\ast (a-4)+4(b+3)$，所以 $a$ 必然小于等于 $4$ 是最优方案。

有不少同学直接钦定 $a=1$ 了，好一点的想到了偶数要求 $a=2$。但实际上简单打个 $1\sim 100$ 的表就容易发现这个结论是错的了。

// 满分
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
// a,b,a+b,(b)+(a+b)
// 3a+4b 接近 n
int a, b, aa, bb;
// 返回 res(res>a) 使得 4*res 尽可能接近 x
int gen(int nowA, int x)
{
	int res1 = max(nowA + 1, x / 4);
	int res2 = max(nowA + 1, x / 4 + 1);
	if (abs(x - res1 * 4) < abs(x - res2 * 4))
		return res1;
	else
		return res2;
}
signed main()
{
	freopen("jie.in", "r", stdin);
	freopen("jie.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	int a = 1, b = 2;
	for (int i = 1; i <= 100; i++) // 实际上 4 就够了
	{
		int j = gen(i, n - 3 * i);
		if (abs(n - 3 * i - 4 * j) < abs(n - 3 * a - 4 * b))
			a = i, b = j;
	}
	cout << a << " " << b << " " << a + b << " " << a + 2 * b << "\n";
	return 0;
}

调虎离山

其实难度没有那么高，不知道有没有后期选手直接上来就 lca 的。

实际上因为是在树上，所以路径是唯一的。就是先向父亲节点方向走到 1-3-7-15-31-... 这条路径上的点，然后往右下走到最终位置即可。发现了这个之后这题就没啥难度了。

有一点容易出问题的地方，怎么判断节点 $x$ 在不在那条路径上。如果直接用 $x+1$ 看是不是 $2$ 的整数次幂，那就可能超过 long long 了。我本来打算卡 unsigned long long，后来想想还是算了。

实际上为了避免上溢出，比较好的做法可能会是像我标程一样直接生成那些位置，然后二分检查。或者直接检查这个数是不是二进制下全是 $1$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, ans;
int a[100000+5];
int R[64]; // 2^i-1
bool check2(int x)
{
	return binary_search(R + 1, R + 63 + 1, x);
}
// 从 pos 到 2^m-1 的路程
int cal(int m, int pos)
{
	int res = 0;
	// 检查 pos+1 是不是 2 的整数次幂
	while (!check2(pos))
	{
		pos /= 2;
		res++;
	}
	while (pos != (1LL << m) - 1)
	{
		pos = pos * 2 + 1;
		res++;
	}
	return res;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	R[0] = 0;
	for (int i = 1; i <= 63; i++)
		R[i] = R[i - 1] * 2 + 1;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	ans = 0;
	for (int i = 1; i <= n; i++)
		ans = max(ans, cal(m, a[i]));
	cout << ans;
	return 0;
}

欲擒姑纵

看懂了程序之后，容易发现 $k=1$ 时，$f(n,k)=n$。所以 $10$ 分很简单。

// 10 分
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
signed main()
{
    freopen("yu.in", "r", stdin);
    freopen("yu.out", "w", stdout);
    int m, k;
    cin >> m >> k;
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = ans ^ i;
    cout << ans;
    return 0;
}

然后很容易发现题面那个代码已经有不少可以优化的地方了。优化后就能拿到不少分数。

// 题面代码优化
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
int f(int n, int k)
{
    if (n == 1)
        return 1;
    for (int x = 2; x <= n; x++) // x>1
        if (n % x == 0)          // x 是 n 的因子
            return f(n / x, k) * x % MOD * k % MOD;
}
signed main()
{
    freopen("yu.in", "r", stdin);
    freopen("yu.out", "w", stdout);
    int m, k;
    cin >> m >> k;
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = ans ^ f(i, k);
    cout << ans;
    return 0;
}

然后有一个比较难的小台阶。需要进一步推，可以得到两种结论（不考虑取模）：

• $f(60,k)=f(30,k)\times 2k=f(15,k)\times 2k\times 2k=f(5,k)\times 3k\times 2k\times 2k=5k\times 3k\times 2k\times 2k=n{k}^4$。
  • 接着可能能想到用埃筛处理出来最小质因子来加速分解质因子，然后 $O(\log n)$ 分解质因子，来拿到 $60$ 分
• 对于质数 $p$ 有 $f(p,k)=pk$。对于其他的 $f(a\times b,k)=f(a)\times f(b)$。（学到后期的同学会知道这是完全积性函数）
  • 那就可以直接在埃筛的同时算出每个数对应的 $f$ 值。

//埃筛 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXM = 20'000'000;
int m, k;
int ans[MAXM + 5];
bool notP[MAXM + 5];
void init()
{
    ans[1] = 1;
    for (int i = 2; i <= m; i++)
    {
        if (notP[i])
            continue;
        ans[i] = i * k % MOD;
        for (int j = 2; j * i <= m; j++)
        {
            ans[j * i] = ans[i] * ans[j] % MOD;
            notP[j * i] = true;
        }
    }
}

signed main()
{
    freopen("yu.in", "r", stdin);
    freopen("yu.out", "w", stdout);
    cin >> m >> k;
    init();
    int sum = 0;
    for (int i = 1; i <= m; i++)
        sum = sum ^ ans[i];
    cout << sum;
    return 0;
}

当然满分是个线性筛的做法，其实这道题出题时我是翻 NOI 大纲，发现线性筛能考，为了考线性筛来构造的函数。

// std
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXM = 20'000'000;
int m, k;
int ans[MAXM + 5];
// 质数数量大概是 n/ln(n)
int tot, p[MAXM / 15 + 5];
bool notP[MAXM + 5];
void init()
{
    tot = 0;
    ans[1] = 1;
    for (int i = 2; i <= m; i++)
    {
        if (!notP[i])
        {
            p[++tot] = i;
            ans[i] = i * k % MOD;
        }
        for (int j = 1; j <= tot && i * p[j] <= m; j++)
        {
            notP[i * p[j]] = true;
            ans[i * p[j]] = ans[i] * ans[p[j]] % MOD;
            if (i % p[j] == 0)
                break;
        }
    }
}

signed main()
{
    freopen("yu.in", "r", stdin);
    freopen("yu.out", "w", stdout);
    cin >> m >> k;
    init();
    int sum = 0;
    for (int i = 1; i <= m; i++)
        sum = sum ^ ans[i];
    cout << sum;
    return 0;
}