【ACM算法竞赛日常训练】DAY7题解与分析【约数个数的和】【[HAOI2011]向量】| 整除分块 | 扩展欧几里得

发布于 2023-03-31  418 次阅读


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\tag{1}$$

单纯考虑y应该满足下面的柿子:

$$a * n_2 + b * m_2 = y\tag{2}$$

当我们两个一起考虑的时候,发现这4个向量,无论选哪一个,都有两种情况:给x + a时,y会+b或-b,给x + b时,y会+a或+b。给y加的时候亦同。那么x+y也会满足一个条件:

$$(a+b) * n_3 + (a-b)*m_3 = x + y\tag{3}$$

当上面三个柿子都有解时,答案为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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞👍、收藏⭐、留言💬