专栏文章

题解：P14304 【MX-J27-T1】分块

UUNNN
P14304题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mini7dwb
此快照首次捕获于
2025/12/02 02:49
3 个月前
此快照最后确认于
2025/12/02 02:49
3 个月前
查看原文
题解交迟了所以没申请

题意

给定一个正整数 nn，求存在多少个正整数 x∈[1,n]x \in [1, n]，使得 x mod ⌊x⌋=0x \bmod \lfloor \sqrt{x} \rfloor = 0。

思路

如果直接暴力搜索，由于 n≤1018n \le 10^{18}，O(n)O(n) 显然会超时。
因此，我们可以考虑手动打表来找规律。我们列出 n=25n = 25 时所有 [1,n][1, n] 的正整数，并判断其是否合法，如下表：
不难发现，对于每一块具有相同的 ⌊x⌋\lfloor \sqrt{x} \rfloor 值的 xx，都仅存在 33 个合法的 xx，这三个数分别是 ⌊x⌋2\lfloor \sqrt{x} \rfloor^2，⌊x⌋2+⌊x+1⌋2−12\frac {\lfloor \sqrt{x} \rfloor^2 + \lfloor \sqrt{x + 1} \rfloor^2 - 1}{2} 和 ⌊x+1⌋2−1\lfloor \sqrt{x + 1} \rfloor^2 - 1。
证明过程
  • 如果 xx 是个完全平方数，那么显然有 ⌊x⌋=x\lfloor \sqrt{x} \rfloor = \sqrt{x}，又因为 x=x⋅x=⌊x⌋⋅⌊x⌋x = \sqrt{x} \cdot \sqrt{x} = \lfloor \sqrt{x} \rfloor \cdot \lfloor \sqrt{x} \rfloor，故 ⌊x⌋\lfloor \sqrt{x} \rfloor 必定是 xx 的一个因数，且 x=⌊x⌋2x = \lfloor \sqrt{x} \rfloor^2。
  • 如果 x+1x + 1 是个完全平方数，根据上述结论有 x+1=⌊x+1⌋2x + 1 = \lfloor \sqrt{x + 1} \rfloor^2，整理可得 x=⌊x+1⌋2−1x = \lfloor \sqrt{x + 1} \rfloor^2 - 1。又因为 x+1x + 1 是完全平方数，所以 xx 不是完全平方数，它们的算术平方根向下取整后显然不一样，而且由于取整，两者会相差 11，所以有 ⌊x+1⌋=⌊x⌋+1\lfloor \sqrt{x + 1} \rfloor = \lfloor \sqrt{x} \rfloor + 1。代入 xx 可以得到以下式子：
x=(⌊x⌋+1)2−1=⌊x⌋2+2⌊x⌋+1−1=⌊x⌋2+2⌊x⌋=⌊x⌋(⌊x⌋+2)\begin{aligned} x &= (\lfloor \sqrt{x} \rfloor + 1)^2 - 1 \\ &= \lfloor \sqrt{x} \rfloor^2 + 2 \lfloor \sqrt{x} \rfloor + 1 - 1 \\ &= \lfloor \sqrt{x} \rfloor^2 + 2 \lfloor \sqrt{x} \rfloor \\ &= \lfloor \sqrt{x} \rfloor(\lfloor \sqrt{x} \rfloor + 2) \end{aligned}
上式中提出了一个因数 ⌊x⌋\lfloor \sqrt{x} \rfloor，所以 ⌊x⌋\lfloor \sqrt{x} \rfloor 必定是 xx 也就是 ⌊x+1⌋2−1\lfloor \sqrt{x + 1} \rfloor^2 - 1 的一个因数。
  • 对于数 ⌊x⌋2+⌊x+1⌋2−12\frac {\lfloor \sqrt{x} \rfloor^2 + \lfloor \sqrt{x + 1} \rfloor^2 - 1}{2}，我们先前已经证明 ⌊x⌋2\lfloor \sqrt{x} \rfloor^2 和 ⌊x+1⌋2−1\lfloor \sqrt{x + 1} \rfloor^2 - 1 在模 ⌊x⌋\lfloor \sqrt{x} \rfloor 意义下同余，故显然两者相加后再乘 22 的逆元依旧在模 ⌊x⌋\lfloor \sqrt{x} \rfloor 意义下同余。
接下来就是统计答案，通过上述的表格可以得知，nn 可以把这若干个 xx 分成 ⌊n⌋\lfloor \sqrt{n} \rfloor 块。我们令 m=⌊n⌋m = \lfloor \sqrt{n} \rfloor，显然前 m−1m - 1 块合法的 xx 总共有 3(m−1)3(m - 1) 个。
对于最后一块，设最后一块有 kk 个合法的数：
  • 如果 nn 在这一块中第一个合法的数 (含) 到第二个合法的数 (不含) 之间，那么 k=1k = 1；
  • 如果在第二个合法的数 (含) 到第三个合法的数 (不含) 之间，那么 k=2k = 2；
  • 如果正好是第三个合法的数，那么 k=3k = 3。
最后答案就是 3(m−1)+k3(m - 1) + k。

Code

CPP
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
ll q, n, m, ans;
bool issq(ll x){ // 判断是否为完全平方数
   ld xx = (ld)sqrt((ld)x);
   return xx == (ll)xx;
}
int main()
{
   scanf("%lld", &q);
   while(q--){
       scanf("%lld", &n);
       m = (ll)sqrt((ld)n); // 计算能分成多少块
       ll l = m * m, r = (m + 1LL) * (m + 1LL), mid = (l + r) >> 1LL; // l, mid, r - 1 分别为最后一块中第一个合法的数，第二个合法的数和第三个合法的数
       // 统计
       if(n >= l && n < mid) ans = (m - 1LL) * 3LL + 1LL;
       else if(n >= mid && n < r - 1LL) ans = (m - 1LL) * 3LL + 2LL;
       else if(n == r - 1LL) ans = m * 3LL;
       printf("%lld\n", ans); // 输出
   }
   return 0; // 结束 (｡･ω･｡)
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...