CCF GESP 2024年3月认证 C++ 8级
题目描述
小 A 写了一个 $N \times M$ 的矩阵 $A$，我们看不到这个矩阵，但我们可以知道，其中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$ 是 $i$ 和 $j$ 的公倍数（$i=1,\dots,N$，$j=1,\dots,M$）。现在有 $K$ 个小朋友，其中第 $k$ 个小朋友想知道，矩阵 $A$ 中最多有多少个元素可以是 $k$（$k=1,2,\dots,K$）。请你帮助这些小朋友求解。
注意：每位小朋友的答案互不相关，例如，有些位置既可能是 $x$，又可能是 $y$，则它同时可以满足 $x,y$ 两名小朋友的要求。
方便起见，你只需要输出 $\sum_{k=1}^{K}{k \times \texttt{ans}_k}$ 即可，其中 $\texttt{ans}_k$ 表示第 $k$ 名小朋友感兴趣的答案。
输入格式
第一行三个正整数 $N,M,K$。
输出格式
输出一行，即 $\sum_{k=1}^{K}{k \times \texttt{ans}_k}$。
请注意，这个数可能很大，使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。
样例说明
样例 1
2 5 29只有 $A_{1,1}$ 可以是 1，其余都不行。
$A_{1,1},A_{1,2},A_{2,1},A_{2,2}$ 都可以是 2，而其余不行。
因此答案是 1×1+2×4=9。
样例 2
100 100 100185233数据范围
对于 30% 的测试点，保证 $N,M,K≤10$；
对于 60% 的测试点，保证 $N,M,K≤500$；
对于 100% 的测试点，保证 $N,M≤10^5，K≤10^6$。
题目描述
小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。
游戏规则是：每张牌上有一个点数 $v$，将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌，则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本身）。
小杨同学现在有一个长度为 $n$ 的卡牌序列 $A$，其中每张牌的点数为 $A_i$（$1\le i\le n$）。小杨同学有 $q$ 次询问。第 $i$ 次（$1\le i\le q$）询问时，小杨同学会给出 $l_i,r_i$ 小杨同学想知道如果用下标在 $[l_i,r_i]$ 的所有卡牌按照下标顺序玩“接竹竿”的游戏，最后队列中剩余的牌数。
输入格式
一行包含一个正整数 $T$，表示测试数据组数。
对于每组测试数据，第一行包含一个正整数 $n$，表示卡牌序列 $A$ 的长度。
第二行包含 $n$ 个正整数 $A_1,A_2,\dots,A_n$，表示卡牌的点数 $A$。
第三行包含一个正整数 $q$，表示询问次数。
接下来 $q$ 行，每行两个正整数 $l_i,r_i$ 表示一组询问。
输出格式
对于每组数据，输出 $q$ 行。第 $i$ 行（$1\le i\le q$）输出一个非负整数，表示第 $i$ 次询问的答案。
样例说明
样例 1
1
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 61
1
0
2对于第一次询问，小杨同学会按照 1,2,2 的顺序放置卡牌，在放置最后一张卡牌时，两张点数为 2 的卡牌会被收走，因此最后队列中只剩余一张点数为 1 的卡牌。
对于第二次询问，队列变化情况为：
{}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}。因此最后队列中只剩余一张点数为 3 的卡牌。
数据范围
对于全部数据，保证有 $1\le T\le 5$，$1\le n\le 1.5\times 10^4$，$1\le q\le 1.5\times 10^4$，$1\le A_i\le 13$。