ICPC 2018 南京网赛 https://nanti.jisuanke.com/t/A2003 Easy Math
标签
递归式
杜教筛
前言
做了这题, 感觉自己又学到了好多东西~
我的 csdn 和博客园是同步的, 欢迎来访 danzh - 博客园 https://www.cnblogs.com/danzh/ ~
简明题意
求
- \[\sum_{
- i=1
- }^{
- m
- }\mu{
- (in)
- }\]
- \(m<=2e9,n<=1e12\)
思路
推式子吧~
首先莫比乌斯函数, 一旦含有平方因子, 他的值就是 - 1. 所以我们可以先特判一下 n 含不含平方因子, 含的话, 答案就是 0.
然后我们看看 n 不含平方因子的情况. 既然 n 没有平方因子, 那么显然 n 是可以分解成 \(p_1p_2...p_n\) 的. 我们任取其中一个质数 p. 然后把原式写成:
\[\sum_{i=1}^{m}\mu{(i*p*\frac{n}{p})}\]
想一想鸡性函数性质 (此处是积不是鸡, 但是鸡太美了所以我就对鸡和积不加区分好了 2333), 鸡性函数 \(g(ab)\), 如果 ab 互质, 则有 \(g(ab)=g(a)g(b)\), 所以我们回到原来的式子, 把 p 提出来, 是不是就成了
\[\sum_{i=1}^{m}\mu{(i*p*\frac{n}{p})}=\sum_{i=1}^{m}\mu{(i*\frac{n}{p})}\mu(p)\]
显然不是的, 因为那个鸡性函数性质, 是需要互质的. 而 p 和 i*n/p 不一定互质鸭! 但是我们先不管这个, 待会再考虑这个. 假设他俩互质了, 一个质数的莫比乌斯函数值一定是 - 1, 我们直接把 - 1 提前, 所以原式:
\[-\sum_{i=1}^{m}\mu{(i*\frac{n}{p})}\]
与索引无关的量可以提到和式前面 (索引是指上式中的 i)
然后我们再回头考虑之前的不互质的情况. p 和 \(i*\frac{n}{p}\) 不互质, 而 p 与 n/p 互质, 可以推出 p|i.(这一步很显然, 可以自己推一下). 也就是说, 对于原式, 上面的式子多减去了不互质的情况, 而且还少加上了不互质的情况. 对于多减去的部分, 我们直接加回去就好了. 但是少加上的部分呢? 少加上的部分是少加上了 \(\sum\limits_{i=1}^{m}\mu{(i*p*\frac{n}{p})}[p|i]\), 这样的话是不是发现 \(\mu\) 又有平方因子了呢, 所以少加上的值我们不用管, 因为他就是 0. 我们只用关心多减去的部分, 加上就好了.
我们把多减去的加回去, 显然原式就是:
\[-\sum_{i=1}^{m}\mu{(i*\frac{n}{p})}+\sum_{i=1}^{m}\mu{(i*\frac{n}{p})}[p|i]\]
然后关注后面的那个式子, 看到后面的条件 \([p|i]\), 是不是立马想到更换枚举上限了? 所以原式就成了:
\[-\sum_{i=1}^{m}\mu{(i*\frac{n}{p})}+\sum_{i=1}^{\frac mp}\mu{(ip*\frac{n}{p})}=-\sum_{i=1}^{m}\mu{(i*\frac{n}{p})}+\sum_{i=1}^{\frac mp}\mu{(in)}\]
我们另 \(S(m,n)=\sum\limits_{i=1}^{m}\mu(in)\), 于是, 我们终于得到了想要的递归式:
\[S(m,n)=-S(m,\frac np)+S(\frac mp,n)\]
这个二元组的边界条件, 就是 S(m,1) 和 S(0,n). 然而 mn 太大, 所以边界直接杜教筛!
注意事项
计算 n 是否含平方因子, 这个时候又 prime[i[*prime[i], 注意别溢出!
总结
一个数没有平方因子等价于 \(n=p_1p_2...p_n\)
我们在计算鸡性函数是, 如果计算的是 \(f(i*n)\), 也就是自变量中含有常数, 我们可以尝试把这个常数分解成 \(p*\frac np\), 从而可以利用鸡性函数性质, 从而进一步转化为递归式
与索引无关的量可以提到和式前面
\(ab|c\), 如果 a 与 c 互质, 那么 \(ab|c \iff b|c\)
对于一个和式, 如果索引必须是某个数的倍数, 那么可以直接更换上限, 然后扩大索引. 比如 \(\sum\limits_{i=1}^{n}[p|i]\), 他等价于 \(\sum\limits_{i=1}^{\frac np}1\)(其中 i 缩小到了原来的 p 倍, 需要乘上)
对于一个二元递归式, 边界条件应该是每一元都到边界
AC 代码
- #include<cstdio>
- #include<unordered_map>
- using namespace std;
- const int maxn = 1e7 + 10;
- long long n, m;
- int prime[maxn], min_p[maxn], mu[maxn], pre_mu[maxn];
- bool no_prime[maxn];
- int shai(int n)
- {
- int cnt = 0;
- no_prime[1] = mu[1] = 1;
- for (int i = 2; i <= n; i++)
- {
- if (!no_prime[i])
- prime[++cnt] = i, mu[i] = -1, min_p[i] = i;
- for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
- {
- no_prime[prime[j] * i] = 1;
- mu[prime[j] * i] = i % prime[j] == 0 ? 0 : -mu[i];
- min_p[prime[j] * i] = prime[j];
- if (i % prime[j] == 0) break;
- }
- }
- for (int i = 1; i <= n; i++)
- pre_mu[i] = pre_mu[i - 1] + mu[i];
- return cnt;
- }
- unordered_map<int, int> rec_mu;
- int cal(int n)//n 的莫比乌斯函数前缀和
- {
- if (n <= maxn - 10) return pre_mu[n];
- if (rec_mu[n]) return rec_mu[n];
- int l = 2, r, ans = 1;
- while (l <= n)
- {
- r = n / (n / l);
- ans -= (r - l + 1) * cal(n / l);
- l = r + 1;
- }
- return rec_mu[n] = ans;
- }
- long long S(long long m, long long n)
- {
- if (m == 0) return 0;
- if (n == 1) return cal(m);
- for (int i = 1; 1ll * prime[i] * prime[i] <= n; i++)
- {
- if (n % prime[i] == 0)
- return -S(m, n / prime[i]) + S(m / prime[i], n);
- }
- return -S(m, n / n) + S(m / n, n);
- }
- void solve()
- {
- int cnt = shai(maxn - 10);
- scanf("%lld%lld", &m, &n);
- for (int i = 1; 1ll * prime[i] * prime[i] <= n; i++)
- if (n % (1ll * prime[i] * prime[i]) == 0)
- {
- printf("0\n");
- return;
- }
- printf("%lld\n", S(m, n));
- }
- int main()
- {
- freopen("Testin.txt", "r", stdin);
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3166626.html