题意
- 一种上下波动的数组，给出所在的位置 \(n\) 和对应的数字 \(x\)，求出有几种数组满足条件。令 \(k\) 为最大值，则数组长成这样子：
- 如图，每 \(2(k-1)\) 就循环一次。
分析
-
因为每 \(2(k-1)\) 个数就循环一次，因此可以列出同余方程 \(n\equiv x\pmod{2(k-1)}\)，若 \(x\neq1\)，则还可以列出 \(n\equiv2k-x\pmod{2(k-1)}\)，可以化成 \(n\equiv2-x\pmod{2(k-1)}\)。
-
因此问题就转化成了怎么求解 \(a\equiv b\pmod x\) 中的 \(x\)。转化一下得 \(a-b\equiv0\pmod x\)，也即 \(x\mid a-b\)，因此答案就是 \(a-b\) 的偶数约数个数。复杂度 \(O(\sqrt n)\)。
-
注意事项：如果 \(k=x\) 时成立的话，在两个式子里都会被统计一次，因此要注意判重。
AC 代码
#include <bits/stdc++.h>
#define int long long
#define inf 1e9
using namespace std;
int x, n;
inline int read(int &x) {
char ch = x = 0;
int m = 1;
while (ch < '0' || ch > '9') {
ch = getchar();
if (ch == '-')
m *= -1;
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar();
}
x *= m;
return x;
}
inline void print(int x) {
if (x < 0)
putchar('-'), x = -x;
static int stk[50];
int top = 0;
do {
stk[top++] = x % 10;
x /= 10;
} while (x);
while (top) {
putchar(stk[--top] + 48);
}
putchar('\n');
return ;
}
inline bool check(int i, int b, int x) {
return !(i & 1) && i > 2 && (i / 2 + 1) >= x && !(b != x && (i / 2 + 1) == x); //注意判重
}
inline int work(int a, int b, int x) {
int m = a - b, res = 0;
for (int i = 1; i * i <= m; i++) {
if (m % i == 0) {
if (check(i, b, x)) res++;
if (check(m / i, b, x)) res++; //记录答案
}
}
return res;
}
signed main() {
int T;
read(T);
while (T--) {
read(n), read(x);
int res = work(n, x, x);
if (x != 1) res += work(n, 2 - x, x); //x 不等于 1 时有另一种可能
if (!((n - x) & 1) && x <= 2) res++; //k=2的方案
print(res);
}
return 0;
}
- 感谢围观！