其实看看数据范围，就是个暴力枚举。
出题时想的是凑数让后期选手写筛写 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;
}
首先 这个应该都很好推。
然后，应该很好想到 暴力枚举的代码。
// 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 循环枚举 的结果，容易发现 必然是 中的一个，此时就可以写出来 的代码了，然后进一步如果能推出 是大于 且最接近 的数，就能 做了有不少同学直接钦定 了，好一点的想到了偶数要求 。但实际上简单打个 的表就容易发现这个结论是错的了。
// 满分
#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-... 这条路径上的点，然后往右下走到最终位置即可。发现了这个之后这题就没啥难度了。
有一点容易出问题的地方，怎么判断节点 在不在那条路径上。如果直接用 看是不是 的整数次幂，那就可能超过 long long 了。我本来打算卡 unsigned long long，后来想想还是算了。
实际上为了避免上溢出，比较好的做法可能会是像我标程一样直接生成那些位置，然后二分检查。或者直接检查这个数是不是二进制下全是 。
#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;
}
看懂了程序之后，容易发现 时，。所以 分很简单。
// 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;
}
然后有一个比较难的小台阶。需要进一步推，可以得到两种结论（不考虑取模）：
//埃筛
#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;
}