跳转至

251004 模拟赛

T1

只需注意到 \(7\times 11\times 13=1001\)，然后简单分讨或者暴力枚举 27 种解（为什么全场只有我一个人没用分讨的）即可。

不开 long long 挂成 \(50\)。

T2

给定两个整数三元组 \(a,b\)，一次操作你可以选择三个数中的某几个数，将他们乘以一个整数或者加上一个整数，问你最少操作多少次可以把 \(a\) 变成 \(b\)。

\(|v|\le 10^9\)

暴力分讨即可。注意到答案不超过 \(3\)，其中 \(0,1\) 都是好判的。对于 \(2\)，先把一个数字相等的情况判掉；分讨两次操作操作的数字是否具有包含关系：若不交，那么枚举操作一个数字，然后对剩下的部分 check1（判断一次能否成功）。若交叉，发现只有很少的情况（一个数字被操作两遍，两个数字被操作一遍），在外面枚举全排列，里面枚举两次操作即可。若包含，先判掉重合的情况；若乘法包含加法，那么加法一定可以放在后面执行，乘法操作三个数，因此可以知道乘数；若加法包含乘法，由于乘法至少也至多对两个数字操作，因此乘数容易得到。

Code

T3

初始给你 \(n\) 个区间 \([l_i,r_i]\)，有 \(q\) 次询问，每次询问给你 \(m\) 个点 \(p_{1\sim m}\)，问你有多少个区间满足其内部恰好包含奇数个点。

\(n,q,l_i,r_i\le 5\times 10^5,~\sum m\le n\)

对 \(m\) 根号分治，设阈值为 \(B\)，对于 \(m\le B\)，发现合法区间形如 \(m^2\) 组限制，由于 \(\sum m^2\) 是 \(nB\) 级别的，因此直接暴力二维数点，用分块平衡即可。对于 \(m>B\)，这样的询问不超过 \(\frac nB\) 个，每次询问直接暴力 \(O(n)\) 扫一遍。时间复杂度 \(O(n\sqrt n)\)。

也可以用别的方法。考虑一个区间对哪些询问有贡献。虽然看着没什么前途，但是如果变化量较小的话还是有办法维护的。用莫队维护，那么上面的东西是容易求得的，但考虑如何合并各区间的贡献。发现莫队扩展的过程形如单点 flip，在 \(0\to 1\) 时贡献提前计算，减掉区间左端点；在 \(1\to 0\) 时再加上区间右端点即可。时间复杂度 \(O(n\sqrt n)\)。虽然跑得没有他们快，但是空间小的离谱（\(13.2\)M）。

Code

T4

给定 \(n\times m\) 的网格图（坐标从 \((1,1)\) 到 \((n,m)\)），问所有顶点在整点上的三角形，轮廓上整点数量之和是多少。

\(n,m\le 10^6,~T\le 5\)

不妨设 \(m\le n\)。

从点或者三角形统计贡献不好做，考虑统计一条边的贡献。对于一条横纵坐标差分别为 \((\Delta x,\Delta y)\) 的边，其上有 \(\gcd(\Delta x,\Delta y)\) 个整点（两个端点只计算一个），而第三个点可以取平面内任意不共线的点，可以取 \(nm\) 个点之后减去共线的情况。共线的情况也是简单的，一个退化成线段的三角形上有 \(2\gcd(\Delta x,\Delta y)\) 个整点，第三个点又可以取所有整点，而取在两个端点上的情况只会把三角形上的其他整点统计一遍，因此加起来也是两遍，正好又是 \(\gcd(x,y)\) 遍。可以列出答案的式子：

\[ \begin{align*} ans1&=\sum_{i=1}^{n}i(n-i)nm(m-1)+\sum_{i=1}^{m}i(m-i)nm(n-1)\\ ans2&=2nm\sum_{x=1}^{n-1}\sum_{y=1}^{m-1}\gcd(x,y)(n-x)(m-y)\\ ans3&=4\sum_{x=1}^{n-1}\sum_{y=1}^{m-1}\gcd(x,y)^2(n-x)(m-y)\\ \end{align*} \]

答案就是 \(ans1+ans2-ans3\)。其中 \(ans2,ans3\) 乘以 \(2\) 是因为线段有两种倾斜方向。

把 \((n-x)(m-y)\) 拆成 \(4\) 项，就变成 P3768 简单的数学题 了，但是由于 \(n,m\) 不等，因此要用莫反。枚举 \(\gcd\)，然后莫反：

\[ \begin{align*} \sum_{d_1=1}^{m}d_1\sum_{x=1}^{\lfloor\frac{n}{d_1}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1}\rfloor}(d_1x)(d_1y) [\gcd(x,y)=1]&=\sum_{d_1=1}^{m}(d_1)^3\sum_{x=1}^{\lfloor\frac{n}{d_1}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1}\rfloor}xy[\gcd(x,y)=1]\\ &=\sum_{d_1=1}^{m}(d_1)^3\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)\sum_{x=1}^{\lfloor\frac{n}{d_1d_2}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1d_2}\rfloor}(d_2x)(d_2y)\\ &=\sum_{d_1=1}^{m}(d_1)^3\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)(d_2)^2\sum_{x=1}^{\lfloor\frac{n}{d_1d_2}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1d_2}\rfloor}xy\\ &=\sum_{d_1=1}^{m}(d_1)^3\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)(d_2)^2\frac{\lfloor\frac{n}{d_1d_2}\rfloor(\lfloor\frac{n}{d_1d_2}\rfloor+1)}{2} \frac{\lfloor\frac{m}{d_1d_2}\rfloor(\lfloor\frac{m}{d_1d_2}\rfloor+1)}{2}\\ \end{align*} \]

考虑到拆 \((n-x)(m-y)\) 出来的四项不尽相同，外面的系数和内部 \(x,y\) 的次数也不一样，但推出来的式子都是如下的形式：

\[ \sum_{d_1=1}^{m}(d_1)^a\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)(d_2)^b\sum_{x=1}^{\lfloor\frac{n}{d_1d_2}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1d_2}\rfloor}x^cy^d \]

反正都能做就是了。

直接整除分块套整除分块，外层 \(d_1\) 内层 \(d_2\)，同时对 \(n,m\) 两个数整除分块即可，时间复杂度 \(O(n+Tn^{3/4})\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#define int __int128
using namespace std;
const int N = 1e6 + 10;

void read(int &x) {
    char ch;
    while(!isdigit(ch = getchar()));
    x = ch - '0';
    while(isdigit(ch = getchar())) x = x * 10 + ch - '0';
}

void write(int x) {
    if(x == 0) putchar('0');
    char buf[60], top = 0;
    while(x) buf[++top] = x % 10, x /= 10;
    while(top) putchar(buf[top--] + '0');
}

int T, n, m;
int ans1, ans2, ans3;

int s[2][N];

int sum(int n, int a) {
    if(a == 0) return n;
    if(a == 1) return n * (n + 1) / 2;
    if(a == 2) return n * (n + 1) * (2 * n + 1) / 6;
    if(a == 3) return s[0][n];
    return s[1][n];
}

int npri[N], pri[N], pcnt;
int mu[N][3];

int calc(int a, int b, int c, int d) {
    int ans = 0;
    for(int l1 = 1, r1; l1 <= m; l1 = r1 + 1) {
        r1 = min(n / (n / l1), m / (m / l1));
        int n1 = n / l1, m1 = m / l1, res = 0;
        for(int l2 = 1, r2; l2 <= m1; l2 = r2 + 1) {
            r2 = min(n1 / (n1 / l2), m1 / (m1 / l2));
            res += (mu[r2][b] - mu[l2 - 1][b]) * sum(n1 / l2, c) * sum(m1 / l2, d);
        }
        ans += res * (sum(r1, a) - sum(l1 - 1, a));
    }
    return ans;
}

void solve() {
    ans1 = ans2 = ans3 = 0;
    if(n < m) swap(n, m);
    for(int i = 1; i <= n; i++) ans1 += i * (n - i) * m * (m - 1) * n;
    for(int i = 1; i <= m; i++) ans1 += i * (m - i) * n * (n - 1) * m;
    ans2 = n * m * calc(1, 0, 0, 0) - n * calc(2, 1, 0, 1) - m * calc(2, 1, 1, 0) + calc(3, 2, 1, 1);
    ans2 = 2 * n * m * ans2;
    ans3 = n * m * calc(2, 0, 0, 0) - n * calc(3, 1, 0, 1) - m * calc(3, 1, 1, 0) + calc(4, 2, 1, 1);
    ans3 = 4 * ans3;
    write(ans1 + ans2 - ans3);
    putchar('\n');
}

signed main() {

    freopen("grid.in", "r", stdin);
    freopen("grid.out", "w", stdout);

    mu[1][0] = 1;
    for(int i = 2; i < N; i++) {
        if(!npri[i]) { mu[i][0] = -1; pri[++pcnt] = i; }
        for(int j = 1; j <= pcnt; j++) {
            if(i * pri[j] >= N) break;
            npri[i * pri[j]] = 1;
            if(i % pri[j] == 0) {
                mu[i * pri[j]][0] = 0;
                break;
            } else {
                mu[i * pri[j]][0] = -mu[i][0];
            }
        }
    }

    for(int i = 1; i < N; i++) mu[i][1] = mu[i - 1][1] + mu[i][0] * i;
    for(int i = 1; i < N; i++) mu[i][2] = mu[i - 1][2] + mu[i][0] * i * i;
    for(int i = 1; i < N; i++) mu[i][0] = mu[i - 1][0] + mu[i][0];

    for(int i = 1; i < N; i++) s[0][i] = s[0][i - 1] + i * i * i;
    for(int i = 1; i < N; i++) s[1][i] = s[1][i - 1] + i * i * i * i;

    read(T);
    while(T--) {
        read(n), read(m);
        solve();
    }

    return 0;
}