DAY7共2题：
- 约数个数的和（和式变换，整除分块）
- [HAOI2011]向量（扩大欧几里得剖析）
难度适中。
作者：Eriktse
简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……）
原文链接（浏览原文取得更好浏览体验）：https://www.eriktse.com/algorithm/1098.html
约数个数的和
题目传送门：https://ac.nowcoder.com/acm/problem/14682
剖析题意咱们能够晓得答案表达式如下：
$$ans=\sum_{i=1}^{n}\sum_{d|i}1$$
其中 $d|i$ 示意d能够整除i，这个柿子的意思是枚举每一个i，而后枚举i的所有约数，找到一个约数，就把答案+1。
然而咱们发现枚举约数是一个不太不便的事儿，咱们能够思考变换求和的指标。
$$ans=\sum_{i=1}^{n}\sum_{d=1}^{n}[d|i]$$
其中 [expression] 是一个布尔函数，当中括号外面的表达式为真时后果为1，反之为0。
然而这样的柿子没有实质的扭转，咱们能够替换求和秩序。
$$ans=\sum_{d=1}^{n}\sum_{i=1}^{n}[d|i]$$
当初咱们能够发现除了d的枚举这一层，剩下的的局部能够进行整除分块，它表白的含意是在d曾经给定的状况下，在[1, n]中有多少个d的倍数。
所以再次变换：
$$ans = \sum_{d=1}^{n}\lfloor\frac{n}{d}\rfloor$$
复杂度为$O(\sqrt{n})$。
对于整除分块的材料：https://oi-wiki.org/math/number-theory/sqrt-decomposition/
#include <bits/stdc++.h>#define int long longusing namespace std;signed main(){ int n;scanf("%lld", &n); int ans = 0; for(int l = 1, r;l <= n; l = r + 1) { r = n / (n / l); ans += (n / l) * (r - l + 1); } printf("%lld\n", ans); return 0;}[HAOI2011]向量
题目传送门：https://ac.nowcoder.com/acm/problem/19985
首先不难发现，这8个向量能够简化为4个：(a, b), (a, -b), (b, a), (b, -a)。
如果单纯思考x的话，应该是满足上面这个柿子：
$$a * n_1 + b * m_1 = x$$
单纯思考y应该满足上面的柿子：
$$a * n_2 + b * m_2 = y$$
当咱们两个一起思考的时候，发现这4个向量，无论选哪一个，都有两种状况：给x + a时，y会+b或-b，给x + b时，y会+a或+b。给y加的时候亦同。那么x+y也会满足一个条件：
$$(a+b) * n_3 + (a-b)*m_3 = x + y$$
当下面三个柿子都有解时，答案为Y，反之为N。
#include <bits/stdc++.h>#define int long longusing namespace std;int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}void solve(){ int a, b, cx, cy;scanf("%lld %lld %lld %lld", &a, &b, &cx, &cy); int d1 = gcd(abs(a), abs(b)), d2 = gcd(abs(a + b), abs(a - b)); if(abs(cx) % d1 || abs(cy) % d1 || abs(cx + cy) % d2)return printf("N\n"), void(); printf("Y\n");}signed main(){ int _;scanf("%lld", &_); while(_ --)solve(); return 0;}本文由eriktse原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言