NOI2016 循环之美（莫比乌斯反演）（杜教筛）

本文主要是介绍NOI2016 循环之美（莫比乌斯反演）（杜教筛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

考虑什么样的 $\frac{x}{y}$ 可以成为纯循环小数
设其循环节为 $L$，那么有
$\frac{x}{y}\ast k^L-\frac{x}{y}$ 为整数
每一对贡献在 $gcd(x,y)=1$ 的时候统计，于是上面这个条件可以转换为
$\exists L,s.t,k^L-1\equiv 0(mody)$
发现这个条件等价于 $gcd(k,y)=1$
推式子，大力莫比乌斯反演
$$Ans=\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)=1][gcd(j,k)=1]$$
$$=\sum _{d=1}^n\mu (d)\lfloor \frac{n}{d}\rfloor \sum _{d|j}[gcd(j,k)=1]$$
$$=\sum _{d=1}^n\mu (d)\lfloor \frac{n}{d}\rfloor \sum _{j=1}^{m/d}[gcd(jd,k)=1]$$
后面的那个 $gcd$ 很明显可以拆成两个
$$=\sum _{d=1}^n\mu (d)\lfloor \frac{n}{d}\rfloor [gcd(d,k)=1]\sum _{j=1}^{m/d}[gcd(j,k)=1]$$
$k$ 很小，后面那坨$f(m/d)$ 可以用 $f(n)=\phi (k)\ast \lfloor \frac{n}{k}\rfloor +f(x\%k)$ $O(1)$ 算
于是有
$$Ans=\sum _{d=1}^n\mu (d)\lfloor \frac{n}{d}\rfloor [gcd(d,k)=1]f(\lfloor \frac{m}{d}\rfloor )$$
如果可以快速求出$g(n,k)={\sum }_{i=1}^n\mu (i)[gcd(i,k)=1]$ 的话，就可以整除分块了
继续莫比乌斯反演
$$g(n,k)=\sum _{i=1}^n\mu (i)[gcd(i,k)=1]$$
$$=\sum _{l|k}\mu (l)\sum _{l|i}\mu (i)$$
$$=\sum _{l|k}\mu (l)\sum _{i=1}^{n/l}\mu (il)$$
这里有一个关于 $\mu (pq)$ 的套路，就是
$$\mu (pq)=\mu (p)\ast \mu (q)\ast [gcd(p,q)=1]$$
意义显然，那么
$$g(n,k)=\sum _{l|k}\mu (l{)}^2\sum _{i=1}^{n/l}\mu (i)[gcd(i,l)=1]$$
看似没有化简，但仔细观察发现后面一坨就是 $g(n/l,l)$
于是有
$$g(n,k)=\sum _{l|k}\mu (l{)}^{2}g(n/l,l)$$
边界条件 $l=1$ 用杜教筛算 $\mu$ 的前缀和就可以了

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int N = 5e6 + 5;
typedef long long ll;
int n, m, k;
int prim[N], mu[N], tot; 
bool isp[N]; ll f[N], g[N], sm[N];
vector<int> fac[N];
int gcd(int a, int b){ return !b ? a : gcd(b, a % b); }
void prework(int n){mu[1] = sm[1] = 1;for(int i = 2; i <= n; i++){if(!isp[i]) prim[++tot] = i, mu[i] = -1;for(int j = 1; j <= tot; j++){if(i * prim[j] > n) break;isp[i * prim[j]] = 1; if(i % prim[j] == 0) break;mu[i * prim[j]] = -mu[i];} sm[i] = sm[i-1] + mu[i];}for(int i = 1; i <= k; i++) for(int j = i; j <= k; j += i) if(mu[i]) fac[j].push_back(i);for(int i = 1; i <= k; i++) g[i] = (gcd(i, k) == 1) + g[i-1];
} 
ll G(int x){ return g[x % k] + (ll)g[k] * (x / k); }
unordered_map<int, ll> sm2;
ll Mu(int x){if(x <= N-5) return sm[x];if(sm2.count(x)) return sm2[x];ll ans = 1; for(int l=2, r; l<=x; l=r+1){int v = x/l; r = x/v;ans -= (ll)(r - l + 1) * Mu(v);} return sm2[x] = ans;
}
unordered_map<int, ll> mp[N];
ll F(int x, int k){if(x == 0) return 0;if(mp[k].count(x)) return mp[k][x];if(k == 1) return mp[k][x] = Mu(x);ll ans = 0;for(int i = 0; i < fac[k].size(); i++){int l = fac[k][i]; ans += F(x/l,l);} return mp[k][x] = ans;
}
int main(){cin >> n >> m >> k; prework(N-5);ll ans = 0;for(int l = 1, r, las = 0, now, lim = min(n,m); l <= lim; l = r+1){int v1 = n/l, v2 = m/l; r = min(n/v1, m/v2);now = F(r, k); ans += 1ll * v1 * G(v2) * (now - las); las = now;} cout << ans; return 0;
} 

这篇关于NOI2016 循环之美（莫比乌斯反演）（杜教筛）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---