Algorithm9.1 数论 数学基础

[TOC]

数论 数学基础

常用：

• 进制转换

数学思维：

1、找到一段序列中出现奇数次/偶数次的

2、找到一段区间中可以用平方差计算得到的个数

进制转换

获取唯一的奇数个的不匹配的数 & 找未配上的对

https://www.luogu.com.cn/problem/P1469 【注意：卡内存，卡时间】

• 思路一：数组存，然后排序，然后再遍历，两个两个遍历=> 爆内存，爆时间。
• 思路二：map存，找到配对的删除。一边即过。=> 6个点爆内存
• 正确思路：直接用一个变量，然后来异或^所有的数，a^a = 0，所以最后剩下的那个数就是没匹配的。

scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &t); ans ^= t;}
printf("%d\n", ans);    

获取唯一的出现偶数次数的 & 找配上对的

这个需要先把所有存在的数都输入进去，得到所有数的异或，然后再异或数组种的所有数，那么出现偶数次的就会显露出来了，出现单次的就会和第一次的异或掉了。

scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &t);ans^=t;}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {scanf("%d", &t);ans^=t;}

区间中可以用平方差计算得到的个数

https://www.luogu.com.cn/problem/P1348

题目大意：区间[a, b]中，某个数i，这个数i可以写成c^2-d^2

正向数学推导：i=(c+d)(c-d)，那么c+d/c-d必定为同奇偶，同奇偶必定乘积要不满足是奇数，要不满足是4的倍数（因为是两个2的倍数相乘）。

反推验证：若i为奇数，也就是2k+1，那么可以找到c=k+1, d=k满足c+d=2k+1与c-d=1的乘积为2k+1这个条件。

若i为4的倍数，也就是4k，那么可以找到c=k+1, d=k-1满足c+d=2k与c-d=2的乘积是4k这个条件。

for (int i = a; i <= b; ++i)
    if (i%2 || !(i%4)) ans++;