DAY7共2题：
约数个数的和（和式变换，整除分块）
[HAOI2011]向量（扩展欧几里得分析）
难度适中。
🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 原文链接（阅读原文获得更好阅读体验）：https://www.eriktse.com/algorithm/1098.html
约数个数的和
题目传送门：https://ac.nowcoder.com/acm/problem/14682
分析题意我们可以知道答案表达式如下：
其中
表示
d可以整除i，这个柿子的意思是枚举每一个i，然后枚举i的所有约数，找到一个约数，就把答案+1。
但是我们发现枚举约数是一个不太方便的事儿，我们可以考虑变换求和的指标。
其中 [expression] 是一个布尔函数，当中括号里面的表达式为真时结果为1，反之为0。
但是这样的柿子没有本质的改变，我们可以交换求和次序。
现在我们可以发现除了d的枚举这一层，剩下的的部分可以进行整除分块，它表达的含义是在d已经给定的情况下，在[1, n]中有多少个d的倍数。
所以再次变换：
复杂度为。
关于整除分块的资料：https://oi-wiki.org/math/number-theory/sqrt-decomposition/
#include <bits/stdc++.h>
#define int long long
using 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的话，应该是满足下面这个柿子：
单纯考虑y应该满足下面的柿子：
当我们两个一起考虑的时候，发现这4个向量，无论选哪一个，都有两种情况：给x + a时，y会+b或-b，给x + b时，y会+a或+b。给y加的时候亦同。那么x+y也会满足一个条件：
当上面三个柿子都有解时，答案为Y，反之为N。
#include <bits/stdc++.h>
#define int long long
using 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原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬
