hdu5468 Puzzled Elena

題意

求一棵子樹內(nèi)與它互質(zhì)的點個數(shù)

解法

容斥

我們先求出與它不互質(zhì)的數(shù)的個數(shù)，再用總數(shù)減去就好。

#include <cstdio> #include <cstring> #include <iostream> #include <vector> using namespace std;namespace Input {int a; char c; bool sign;inline int geti() {sign = false;while ((c = getchar()) < '0' || c > '9') sign |= c == '-';a = c - '0';while ((c = getchar()) >= '0' && c <= '9') a = (a << 3) + (a << 1) + c - '0';return sign ? -a : a;} }const int N = 1e5 + 5; vector<int> edge[N], Num[N], ty[N]; int Cnt[N], Val[N], ans[N], ch[N][70];void init() {memset(Cnt, 1, sizeof Cnt);int i, j, cnt, len, t, k; cnt = 0;for (i = 0; i < N; ++i) Num[i].clear(), ty[i].clear();for (i = 2; i < N; ++i) {if (Cnt[i]) {for (j = i; j < N; j += i)Cnt[j] = 0, Num[j].push_back(i), cnt += j == 4;}}vector<int>tmp;for (i = 2; i < N; ++i) {tmp.clear();for (j = 0; j < Num[i].size(); ++j)tmp.push_back(Num[i][j]);len = tmp.size(); Num[i].clear();for (j = 1; j < (1 << len); ++j) {cnt = 0, t = 1;for (k = 0; k < len; ++k)if (j & (1 << k)) {++cnt; t *= tmp[k];}if (cnt & 1) ty[i].push_back(-1);else ty[i].push_back(1);Num[i].push_back(t);}} }int dfs(int u, int fa) {int si = 0, va = Val[u], i, v;for (i = 0; i < Num[va].size(); ++i)ch[u][i] = Cnt[Num[va][i]];for (i = 0; i < edge[u].size(); ++i) {v = edge[u][i];if (v == fa) continue;si += dfs(v, u);}ans[u] = si;for (i = 0; i < Num[va].size(); ++i)ans[u] += Cnt[Num[va][i]] - ch[u][i];for (i = 0; i < Num[va].size(); ++i)Cnt[Num[va][i]] += ty[va][i];if (va == 1) ++ans[u];return si + 1; }int main() {init();int Case = 0, n, u, v, i;while (scanf("%d", &n) ^ EOF) {for (i = 1; i <= n; ++i) edge[i].clear();for (i = 1; i < n; ++i) {u = Input::geti(), v = Input::geti();edge[u].push_back(v), edge[v].push_back(u);}memset(Cnt, 0, sizeof Cnt);for (i = 1; i <= n; ++i) Val[i] = Input::geti();dfs(1, 0);printf("Case #%d:", ++Case);for (i = 1; i <= n; ++i)printf(" %d", ans[i]);puts("");}return 0; }

莫比烏斯反演

此題其實也可以用莫比烏斯反演做，不過其實與容斥差不多，因為mu[i]其實與ty[i]是一樣的。
代碼就不貼了，其實比較像。

轉(zhuǎn)載于:https://www.cnblogs.com/cycleke/p/5838879.html

總結(jié)

以上是生活随笔為你收集整理的hdu5468 Puzzled Elena的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。