算法总结——基础数论1

program_xwl · 2024-07-09 11:59:30 · 算法·理论

基础数论其实就是基础数学。用它的出的题是真的恶心

公式：

两点之间距离公式（勾股定理）：

其实不一定只有两个维度，三维，四维只要把公式改一点点就行了。比如三维：

三角形面积公式（海伦公式）：

幂的基本性质：

异或：

异或应该是位运算里面最常用的吧，它可以理解为2进制中不进位的加法。

异或的基本性质：

唯一分解定理：

一个大于等于1的正整数必定可以唯一拆分为若干个质因子相乘。

如果b\mid a(a能被b整除)，那么：

• ### $a$不能被整除的话，可能含有公共质因子$gcd$唯一分解。 ### $1$个数最多只有一个大于等于其根的质因子。 ## 例题1 [P1469 找筷子](https://www.luogu.com.cn/problem/P1469) #### 这题$n$的范围是$10^7+1$，空间限制却只有$4MB$，数组都开不下，也就是说它只准我们读一遍。 #### 要用什么方法写这题呢？答案是异或，我们拿出这四条公式： $$ \begin{cases} &a\oplus 0=a\\ &a\oplus a=0\\ &a\oplus b = b \oplus a\\ &a\oplus b \oplus c = a \oplus (b \oplus c) \end{cases} $$ #### 相同的异或得$0$，任何数异或$0$都得原数。我们可以运用异或的交换律和结合律来让它们相同的全部抵消，然后就只剩落单的没数和它抵消了，所以，把所有筷子的长度全部异或起来就是答案。 #### 就拿样例来演示一下吧。 $$ 2\oplus 2\oplus 1\oplus 3\oplus 3\oplus 3\oplus 2\oplus 3\oplus 1\\ =(1\oplus 1)\oplus (2\oplus 2\oplus 2)\oplus (3\oplus 3\oplus 3\oplus 3)\\ =(0)\oplus (0)\oplus (2)\oplus (0)\\ =2 $$ #### 样例答案确实是$2$。 #### 而且，这题卡cin，不用scanf会TLE一个点 ### 代码： ```cpp #include <bits/stdc++.h> using namespace std;

int n,ans = 0;

int main(void) { scanf("%d",&n); for(int i = 1;i <= n;i++) { int x; scanf("%d",&x); ans ^= x; } cout << ans; return 0; }

## 例题2 [B3715 分解质因子 2](https://www.luogu.com.cn/problem/B3715)
#### 这题可以从小到大枚举质因子，发现一个合法的就输出并将$n$除以这个质因子，防止重复输出。通过唯一基本定理可知我们只需要枚举到$\sqrt{n}$如果最后$n$大于$1$这是它就是那个大于等于$\sqrt{n}$的质因子，输出即可。
### 代码：
```cpp
#include <bits/stdc++.h>
using namespace std;

int T;

int main(void)
{
    cin >> T;
    while(T--)
    {
        long long n;
        cin >> n;
        for(long long i = 2;i*i <= n;i++)
        {
            while(n % i == 0)
            {
                n /= i;
                cout << i << ' ';
            }
        }
        if(n > 1) cout << n;
        cout << '\n';
    }
    return 0;
}

数学还是非常重要的。