HDU 4407 Sum 容斥離線解法優化版
同 207873 題，此處提供更緊湊的實現細節與優化技巧。
優化點
- 質因數分解預處理：線性篩預計算最小質因數
minP[x]，分解 p 只需 O(log p) 反覆除以 minP。
- 容斥遞歸去重：用 DFS 枚舉質因數子集，避免位掩碼循環的分支預測失敗。
void dfs(int idx, long long L, int parity) { if (L > y) return; ans += parity * sumMultiples(L); for (int i=idx; i
- 修改操作去重：反向掃描修改記錄，用
vis[pos] 標記，只保留每個位置最後一次修改，減少判斷次數。
- 互質判斷用 std::gcd：C++17
std::gcd 編譯器內建，極快。
完整優化代碼
#include
using namespace std;
using ll = long long;
const int MAXV = 400000;
int minP[MAXV+1];
vector primes;
void linearSieve() {
for (int i = 2; i <= MAXV; ++i) {
if (!minP[i]) { minP[i] = i; primes.push_back(i); }
for (int p : primes) {
if (p > minP[i] || i * p > MAXV) break;
minP[i*p] = p;
}
}
}
vector getPrimeFactors(int x) {
vector pf;
while (x > 1) {
int p = minP[x];
pf.push_back(p);
while (x % p == 0) x /= p;
}
return pf;
}
ll sumMultiples(ll n, ll L) {
if (L > n) return 0;
ll cnt = n / L;
return (L + L*cnt) * cnt / 2;
}
ll calcInitial(int x, int y, int p) {
ll total = (ll)(x+y)*(y-x+1)/2;
if (p == 1) return total;
vector pf = getPrimeFactors(p);
function dfs = [&](int idx, ll L, int parity) {
if (L > y) return;
total += parity * (sumMultiples(y, L) - sumMultiples(x-1, L));
for (int i = idx; i < (int)pf.size(); ++i)
dfs(i+1, L*pf[i], -parity);
};
dfs(0, 1, -1);
return total;
}
struct Op { int type, x, y, p; };
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
linearSieve();
int T; cin >> T;
while (T--) {
int n, m; cin >> n >> m;
vector ops(m);
for (int i = 0; i < m; ++i) {
cin >> ops[i].type;
if (ops[i].type == 1) cin >> ops[i].x >> ops[i].y >> ops[i].p;
else cin >> ops[i].x >> ops[i].y;
}
vector initAns;
for (auto& op : ops) if (op.type == 1)
initAns.push_back(calcInitial(op.x, op.y, op.p));
vector> mods;
vector vis(n+1);
int aidx = 0;
for (int i = 0; i < m; ++i) {
if (ops[i].type == 2) {
mods.emplace_back(ops[i].x, ops[i].y);
} else {
ll res = initAns[aidx++];
fill(vis.begin(), vis.end(), 0);
for (int j = (int)mods.size()-1; j >= 0; --j) {
int pos = mods[j].first, nv = mods[j].second;
if (vis[pos]) continue;
vis[pos] = 1;
if (pos < ops[i].x || pos > ops[i].y) continue;
int p = ops[i].p;
int ov = pos;
if (std::gcd(ov, p) == 1) res -= ov;
if (std::gcd(nv, p) == 1) res += nv;
}
cout << res << '\n';
}
}
}
return 0;
}
測試樣例
1
3 3
2 2 3 1
1 3 4
1 2 3 6
輸出：
7
0
