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 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
的话,应该是满足上面这个柿子:
$$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 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 原创,创作不易,如果对您有帮忙,欢送小伙伴们点赞👍、珍藏⭐、留言💬