关于acm:ACM算法竞赛日常训练DAY7题解与分析约数个数的和HAOI2011向量-整除分块-扩展欧几里得

95次阅读

共计 1668 个字符，预计需要花费 5 分钟才能阅读完成。

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;
}

题目传送门：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;
}