T2 開平方
要證明“$x$ 能表示為兩個平方數之差當且僅當 $x$ 是奇數或4的倍數”，需從以下兩方面分析：
1. 充分性（滿足條件的數一定能表示為平方差）
奇數：
設 $x = 2k + 1$（$k$ 為整數）。取 $y = k + 1$，$z = k$，則：
$y^2 - z^2 = (k + 1)^2 - k^2 = 2k + 1 = x.$
因此，所有奇數均可表示為平方差。
4的倍數：
設 $x = 4k$（$k$ 為整數）。取 $y = k + 1$，$z = k - 1$，則:
$y^2 - z^2 = (k + 1)^2 - (k - 1)^2 = 4k = x.$
因此，所有4的倍數均可表示為平方差。
2. 必要性（能表示為平方差的數必為奇數或4的倍數）
平方差公式為 $x = (y - z)(y + z)$，令 $a = y - z$，$b = y + z$，則 $a$ 和 $b$ 需滿足：
1. $a$ 和 $b$ 同奇偶性：
因為 $a + b = 2y$ 必須為偶數，所以 $a$ 和 $b$ 同為奇數或同為偶數。
2. $x = a \cdot b$：
若 $a$ 和 $b$ 均為奇數，則 $x$ = 奇數 $\times$ 奇數 = 奇數。
若 $a$ 和 $b$ 均為偶數，設 $a = 2m$，$b = 2n$，則 $x = 4mn$，即 $x$ 為4的倍數。
綜上，若 $x$ 可表示為平方差，則 $x$ 必為奇數或4的倍數。
---
結論
充要條件 ：$x$ 能表示為兩個平方數之差當且僅當 $x$ 是奇數或4的倍數。
code
#include <bits/stdc++.h>
using namespace std;
signed main() {
int L, R;
cin >> L >> R;
// 計算奇數個數
int odd = (R + 1) / 2 - L / 2;
// 計算4的倍數個數
int mul4 = R / 4 - (L - 1) / 4;
cout << odd + mul4;
return 0;
}
T4 異或
ans = 第k位【 x(x<=n)中的1 】* 【 y(y<=m)中的0】 + 【x(x<=n)中的0】 *【 y(y<=m)】中的1 * (1<<k)
```
for (int i = 0; i <= 60; ++i) {//周期規律 000...111
LL x = 1LL << (i + 1LL);//周期的大小
LL y = x>>1; //周期大小的一半
LL c = (n + 1LL)/x; //有多少個完整的周期
LL p = (n + 1LL)%x; //不完整的部分
ua[i] = (c * y % M + max(p - y, 0LL) % M) % M;//完整的周期個數 * 周期的一半 + 不完整的部分 - 周期的一半
ub[i] = (n - ua[i]) % M;
}
```
查看代碼
#include<bitsstdc++.h>
#define LL long long
using namespace std;
const int N = 67;
const LL M = 998244353;
int T;
LL n, m, ua[N], ub[N], va[N], vb[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld%lld", &n, &m);
for (int i = 0; i <= 60; ++i) {//周期規律 000...111
LL x = 1LL << (i + 1LL);//周期的大小
LL y = x>>1; //周期大小的一半
LL c = (n + 1LL)/x; //有多少個完整的周期
LL p = (n + 1LL)%x; //不完整的部分
ua[i] = (c * y % M + max(p - y, 0LL) % M) % M;//完整的周期個數 * 周期的一半 + 不完整的部分 - 周期的一半
ub[i] = (n - ua[i]) % M;
}
for (int i = 0; i <= 60; ++i) {
LL x = 1LL << (i + 1LL);//周期的大小
LL y = x>>1; //周期大小的一半
LL c = (m + 1LL)/x; //有多少個完整的周期
LL p = (m + 1LL)%x; //不完整的部分
va[i] = (c * y % M + max(p - y, 0LL) % M) % M;//完整的周期個數 * 周期的一半 + 不完整的部分 - 周期的一半
vb[i] = (m - va[i]) % M;
}
LL ans = 0;
for (int i = 0; i <= 60; ++i)
(ans += (ua[i] * vb[i] % M + ub[i] * va[i] % M) % M * ((1LL << i) % M)) %= M;
printf("%lld\n", ans);
}
return 0;
}
浙公網安備 33010602011771號