头像

咲张熊猫人




离线:8小时前



求一个数的约数(试除法求约数)

跟判断一个数是否是质数一样,同样采用试除法来判断

练习链接: 869. 试除法求约数

#include<iostream>
#include<algorithm>
#include<vector>        
using namespace std;

auto f(int n)
{
    vector<int> v;
    for(int i = 1; i <= n / i; ++i) // 同样因数的话只用判断一半, 因为判断出一个因数时,也同时得到了另外一个因数
    {
        if(n % i == 0)
        {
            v.push_back(i);
            if(i != n / i) v.push_back(n / i);  // 特判开根号的情况
        }
    }
    sort(v.begin(), v.end());       // 题目要求从小到大输出
    for(auto a: v) cout << a << " ";
    cout << endl;
}

auto main() -> int
{
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        f(a);
    }
}

约数的个数

其实这就是一个公式 : 约数个数定理
1.png
首先根据定义,n可以分解质因数:n=p1^a1×p2^a2×p3^a3pk^ak,
其中一个因数为 n=p1^b1×p2^b2×p3^b3pk^bk 故此时对于b1可以在 (0 ~ a1)间取值,共a1 + 1 种, 同理b2 也有 a2 + 1 种取值. 故根据乘法原理:n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。

练习链接 : 870. 约数个数

#include<iostream>
#include<unordered_map>
using namespace std;
constexpr int mod = 1e+9 + 7;

// 故根据上面的公式我们只要把要求的数分解成底数和其对应的指数即可

auto main() -> int
{
    unordered_map<int, int> m;
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        for(int i = 2; i <= a / i; ++i) 
            while(a % i == 0) m[i]++, a /= i;   // map数组first记录底数, second 记录指数
        if(a > 1) m[a]++;      
    }

    long long res = 1;
    for(auto item : m) res = res * (item.second + 1) % mod;  // 根据公式进行计算
    cout << res << endl;
    return 0;
}

约数之和 –> 约数和定理

约数和定理: 对于一个大于1正整数n可以分解质因数:n=p1^a1p2^a2p3^a3pk^ak,那么其正约数和为
f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak)

练习链接: 871. 约数之和

#include<iostream>
#include<unordered_map>
using namespace std;
constexpr int mod = 1e+9 + 7;

auto main() -> int
{
    unordered_map<int, int> m;
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        for(int i = 2; i <= a / i; ++i)
            while(a % i == 0) m[i]++, a /= i;   // 跟之前求约数个数一样,先对这个数进行分解,分解成底数和指数的格式
        if(a > 1) m[a]++;
    }

    long long res = 1;
    for(auto item : m)
    {
        long long t = 1;
        for(int i = 1; i <= item.second; ++i)
            t = (t * item.first + 1) % mod;    // 相当于算出(pk0 + pk1 + pk2 + ... + pkx);
        res = res * t % mod;     // 根据约数和公式将这些项相乘
    }
    cout << res << endl;
}

求最大公约数 (辗转相除法 / 欧几里得算法)

首先来看这样一个例子, d能整除a, 记做 d | a, 同样d能整除b, 记 d | b, 故同样得到的一个结论就是 d | xa + yb, 这是一个基本的性质了。 故现在要推导的一个定理为(a, b) 的最大公约数等于 (a. a mod b) 的最大公约数, 首先我们看 (a, b), 其中一个公约数为d, 故对于左边 d | a, d | b, 对于(a, a mod b),同样是d | a (因为这一项跟左边是一样的一项, 那 d | a mod b 吗? 我们将 a mod b 展开一下 a mod b = a - | a / b | * b (这里| a / b | 表示下取整,直接记为c = | a / b | 故 a mod b = a - c * b; 故d一定可以整除 , d | a - c * b; 这说明左边的公约数一定是右边的公约数, 那么右边的公约数是左边的公约数吗, 从右边看,(b, a mod b), 即(b, a - c * b)的公约数为d, 则存在 d | b , d | a - c * b; 故对于左边d | b 一定成立, 那么再看 d | a - c * b , 由于已经存在了 d | b , 故再加上c * b , d | a - c * b + c * b 还是成立的,故得到了 d | a, 故这就证明了右边的公约数也是左边的公约数,两边的公约数一样,那么其最大公约数肯定也一样。故这样的话只需一行代码即可求出两个数的最大公约数

练习链接: 872. 最大公约数

#include<iostream>
using namespace std;

auto f(int a, int b) -> int
{
// 判断一下此时第二项是否为0, 若为0,(1)上来就是b = 0直接返回a即可,因为0的因数可以是任何其他数
// (1)若不是继续递归, 根据上面的推导 (a, b) 和 (b, a mod b) 的最大公约数相同
// 直到第二项等于0时, 也就对应第一项是最大的了
    return b ? f(b, a % b) : a;   
}

auto main() -> int
{
    int n; cin >> n;
    while(n--)
    {
        int a, b; cin >> a >> b;
        cout << f(a, b) << endl;
    }
}



判断质数 Prime

练习链接: 866. 试除法判定质数

// 很简单, 常用就是试除法,这里主要强调一下细节
#include<iostream>
using namespace std;

auto is_prime(int x) -> bool     
{
    if(x < 2) return false;           // 小于2的数既不是合数也不是质数

     // 这里只要判断前半部分就好了,直接写成开根号太难看,写成 i * i <= x, 如果i很大则会溢出,
     // 故写成这样最好,注意等于条件,判断的是刚好平方等于这个数
    for(int i = 2; i <= x / i; ++i)  
        if(x % i == 0) return false;
    return true;
}

auto main() -> int
{
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        if(is_prime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

分解质因数

质因数概念, 首先它是一个因数,然后这个因数是质数,例如18的质因数只有 2 , 3, 简单的概念了

练习链接: 867. 分解质因数

#include<iostream>
using namespace std;

auto main() -> int
{
    int n;
    cin >> n;
    while(n--)
    {
        int a; cin >> a;
        if(a < 2)
        {
            cout << endl;
            continue;
        }

        // 思路:既然是找质因数,故从最小的质数2开始看能不能整除,同样试除法
        // 那为啥是从2,++i, 这样不会循环到合数吗,如何保证循环到的是质数呢
        // 因为如果找到一个能整除的数之后我们会进入while把这个数有包含i的部分
        // 给除干净了,所以当循环到i的时候就说明此时的a, 绝对不包含 2 ~ i 的因数
        // 而如果 i 能够整除的话,肯定说明 i 的因数没有2 ~ i 的因数不然不可能整除
        // i 的因数没有2 ~ i 的因数,所以也就说明了i只有1和本身i这两个因数,这不就是质数的定义吗
        // 这里同样做了次处理一半的处理,因为如果前一半都没有因数,那么后面就不可能有
        for(int i = 2; i <= a / i; ++i)    
        {
            int c = 0;
            if(a % i == 0)
            {
                while(a % i == 0) a /= i, c++;
                cout << i << " " << c << endl;
            }
        }
        if(a > 1) cout << a << " " << 1 << endl;
        cout << endl;
    }
    return 0;
}

筛质数 (在一个范围内快速筛选出质数)

相比于判断质数,我们不能在一个范围内一个一个采用试除法判断,因为时间复杂度会很高

这里主要有两种筛法: 1. 埃氏筛法 (朴素筛法), 2. 欧拉筛法 (线性筛)

1. 埃氏筛法

从最小的质数2开始, 我们知道合数一定是质数的倍数,故我们将筛选到的第一个质数时,我们将它的倍数依次标记为合数,当然不用全部标,只用标记到给出的范围即可. 由于是从最小质数开始,故找到的下一个未被标记的数一定也是质数,因为未被标记说明不含2 ~ i - 1 的任何因数,跟上面原理一样。 故将找到的这个新的质数的倍数标记为合数。代码实现

#include<iostream>
using namespace std;

constexpr int N = 1e+6 + 10;
bool st[N];

auto f(int n) -> int
{
    if(n < 2) return 0;
    int cnt = 0;
    for(int i = 2; i <= n; ++i)
    {   
        if(st[i]) continue;
        st[i] = true; cnt++;
        // 这里的话如果在数据不大的情况下可以做个优化, int j = i * i 从这里开始
        // 因为前面的2 ~ i - 1 中,如果是倍数的情况已经标记过了,故从i * i 开始
        // 但这里这样优化的话,i * i 可能会溢出,故这样写保证了不溢出
        for(int j = i + i ; j <= n; j += i)     // 将其倍数标记为合数
            st[j] = true;
    }
    return cnt;
}

auto main() -> int
{
    int n; cin >> n;
    cout << f(n) << endl;
}

1. 欧拉筛

通过观察上面的埃氏筛,我们可以发现其实存在重复标记的情况,例如6这个数字,在2的时候会被标记一次,在3的时候也会被标记一次,故欧拉筛,也叫线性筛,保证了每个合数只被最小的质因数筛掉,即每一个合数只会被标记一次. 其实现原理直接来看代码讲解其相较于上面的算法如何改进

#include<iostream>
using namespace std;
constexpr int N = 1e+6 + 10;
int p[N];
bool st[N];

auto f(int n) -> int
{
    if(n < 2)  return 0;
    int cnt = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i]) p[++cnt] = i;    // 相比于上面的算法,这里额外多了一个p数组用来保存当前的质数
        for(int j = 1; p[j] <= n / i; ++j)     
        {
            st[i * p[j]] = true; // 每次for将p数组中质数的倍数标记为合数, 这一步貌似跟埃氏筛没啥区别
            if(i % p[j] == 0) break;  // 这一步是这个算法的核心,理解为啥欧拉筛每个数只被标记一次

// 我们首先来看, 如果没有这个if特判break退出会咋样,当 i 能被p[j]整除时,设 m = i / p[j];
// 故我们得到了 i = m * p[j], 然后我们的for继续,则标记下一个合数为 i * p[j + 1] , 将我们的i代入得
//  m * p[j] * p[j + 1] --->  (m * p[j + 1]) * p[j], 故这里我们就发现了当我们的i循环到 i = (m * p[j + 1]) 时又会被标记一次,
// 同理 i * p[j + 2] .....也是这种情况, 故这里break退出, 因为后面会会标记. 这样就保证了每个数只会被最小的质因数筛选掉

        }
    }
    return cnt;
}

auto main() -> int
{
    int n; cin >> n;
    cout << f(n) << endl;
    return 0;
}


活动打卡代码 AcWing 871. 约数之和

#include<iostream>
#include<unordered_map>
using namespace std;
constexpr int mod = 1e+9 + 7;

auto main() -> int
{
    unordered_map<int, int> m;
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        for(int i = 2; i <= a / i; ++i)
            while(a % i == 0) m[i]++, a /= i;
        if(a > 1) m[a]++;
    }
    long long res = 1;
    for(auto item : m)
    {
        long long t = 1;
        for(int i = 1; i <= item.second; ++i)
            t = (t * item.first + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;
}



活动打卡代码 AcWing 870. 约数个数

#include<iostream>
#include<unordered_map>
using namespace std;

constexpr int mod = 1e+9 + 7;

auto main() -> int
{
    unordered_map<int, int> m;
    int n; cin >> n;
    long long res = 1;

#if 1
    while(n--)
    {
        int a; cin >> a;
        for(int i = 2; i <= a / i; ++i)
            while(a % i == 0) m[i]++, a /= i;
         if(a > 1) m[a]++;
    }
#endif 
    for(auto item : m) res = res * (item.second + 1) % mod;
    cout << res << endl;
}


活动打卡代码 AcWing 872. 最大公约数

#include<iostream>
using namespace std;
auto f (int a, int b) -> int
{
  return b ? f(b, a % b) : a;
};

auto main() -> int
{
    int n; cin >> n;

    while(n--)
    {
        int a, b; cin >> a >> b;
        cout << f(a, b) << endl;
    }

    return 0;
}


活动打卡代码 AcWing 869. 试除法求约数

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

auto f(int n)
{
    vector<int> v;
    for(int i = 1; i <= n / i; ++i)
    {
        if(n % i == 0) 
        {
            v.push_back(i);
            if(i != n / i) v.push_back(n / i);
        }
    }
    sort(v.begin(), v.end());
    for(auto a : v) cout << a << " ";
    cout << endl;
}

auto main() -> int
{
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        f(a);
    }
    return 0;
}


活动打卡代码 AcWing 868. 筛质数

#include<iostream>
using namespace std;
constexpr int N = 1e+7 + 10;
int p[N];
bool st[N];

auto f(int n) -> int
{
    if(n < 2) return 0;
    int cnt = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(!st[i]) p[++cnt] = i;
        for(int j = 1; p[j] <= n / i; ++j)
        {
            st[i * p[j]] = true;
            if(i % p[j] == 0) break;
        }
    }
    return cnt;
}

auto main() -> int
{
    int n; cin >> n;
    cout << f(n) << endl;
    return 0;
} 


活动打卡代码 AcWing 867. 分解质因数

#include<iostream>
using namespace std;

auto prime(int x) 
{
    if(x < 2) return;

    for(int i = 2; i <= x / i; ++i)
    {
        int res = 0;
        if(x % i == 0)
        {
            while(x % i == 0)
            {
                x /= i;
                ++res;
            }
            cout << i << " " << res << endl;
        }
    }
    if(x > 1) cout << x << " " << 1 << endl; 
}

auto main() -> int
{
    int n; cin >> n;
    while(n--)
    {
        int a; cin >> a;
        prime(a);
        cout << endl;
    }
    return 0;
}



#include<iostream>
using namespace std;

int n;

auto is_prime(int x) -> bool
{
    if(x < 2) return false;
    for(int i = 2; i <= x / i; ++i)
        if(x % i == 0) return false;
    return true;
}

auto main() -> int
{
    cin >> n;
    while(n--)
    {
        int a; cin >> a;
        if(is_prime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}



二分图

  |------------染色法 O(n2)
  |                          
  | 
  | 
  |
  二分图相关算法    
  |
  |
  |
  |
  |----------- 匈牙利算法 (最坏O(mn), 但实际运行效果较好,远小于mn)

首先搞清楚二分图的概念,简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。
5.png

二分图中的一个重要性质: 若一个图中存在奇数环(即存在节点数为奇数个的环),则该图不可能是二分图。 因为根据二分图的定义,若要保证两个集合的中间不存在节点,故每一条边的两个端点必定是不同的部分,若存在奇数环,则从任意一个点开始,标记为1,表示左半部分,然后其连接的下一节点必定为右部分,标记为2,依次类推再下一个标记为1,若为奇数环,则就会出现矛盾的情况。

染色法

其实就是上面分析性质的过程,遍历所有的节点,然后遍历其连接的下一节点,依次标记为不同的颜色,这里的话在算法实现上dfs和bfs都是可以的,若在这个过程中出现矛盾的情况则表示该图不为二分图.

练习链接: 860. 染色法判定二分图
代码实现

#include<iostream>
#include<cstring>
using namespace std;

constexpr int N = 2e+5 + 10;

int n,m,g[N], e[N], ne[N], idx; // 为了方便遍历一个节点所相连的其他节点,这里采用邻接表储存
int color[N];

auto add(int a, int b)
{
    e[idx] = b, ne[idx] = g[a], g[a] = idx++;
}


auto dfs(int u, int c) -> bool    // 这里采用dfs遍历每个节点及其所相连的节点
{
    color[u] = c;
    for(int i = g[u]; i != -1; i = ne[i])   // 依次遍历u节点所相连的其他节点    
    {
        int t = e[i]; 
        if(!color[t])             // 若该节点为被染色, 则进行染色, 1, 2代表两种颜色
        {
            if(!dfs(t, 3 - c)) return false;   // 3 - c 表示染上和c不同的颜色
        }
        else if(color[t] == c) return false;   // 若该节点未被染色并且和上一节点颜色相同则矛盾
    }
    return true;
}

auto main() -> int
{
    memset(g, -1, sizeof g);
    cin >> n >> m;
    while(m--)
    {
        int a, b; cin >> a >> b;
        add(a, b), add(b,a);
    }
    for(int i = 1; i <= n; ++i)   // 依次遍历每一个节点
    {
        if(!color[i])
        {
            if(!dfs(i, 1))        // 若出现冒充直接goto到end结束
            { 
                cout << "No" << endl;
                goto end;
            }
        }
    }
    cout << "Yes" << endl; 
end:
    return 0;
}

匈牙利算法

匈牙利算法主要解决二分图中的最大匹配问题,首先来了解一下什么叫二分图的匹配, 给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
6.png
如左图所示的是一个二分图,可以分为左部分集合为 u, 右半部分集合为v, 然后根据匹配的定义,任意两条边都不依附于同一个顶点。我们可以看到左图的5号顶点中,有三条边依附于5号节点上, 2条边依附于7号节点上。 故这些边并不能算作是一种匹配的情况,故在右图的情况中属于图的一个边集, 即符合匹配的条件,且最大匹配数即为为4条边,故结果为4.

故匈牙利算法的思路: 模拟一下算法的过程, 首先从原本的二分图中,我们看作是遍历作半部分的节点,然后找到唯一一个与其匹配的右边节点,例如从左图中1号节点可以匹配5号节点和7号节点,故先让其匹配5号节点,此时算作一个匹配,然后遍历左边的下一节点2,此时它只能与5号点匹配,但是5号节点已经和1号点匹配,此时再考虑1号点有没有其他匹配的方案,发现1号点可以和7号匹配,故1号重新和7号匹配,2号和5号匹配, 故此时已经有两个匹配,然后继续遍历左边剩余节点,此时遍历3号节点,3号节与5号节点和6号节点相连,我们从上到下的顺序依次判断,首先是5号节点,此时5号节点已经和2号节点匹配,然后回去判断2号节点是否能和其他节点匹配,发现没有其他节点符合条件,故此时再判断6号节点,发现还没有其他节点与其匹配,故匹配成功。继续遍历左边的剩余节点。此时剩下4号节点,与其相连的节点有7号节点和8号节点,首先判断是否能和7号节点匹配,发现7号节点已经和1号节点匹配,故看看1号节点能不能和其他节点匹配,发现其能和5号节点匹配,但5号节点已经和2号节点匹配,故再看看2号节点能不能换一个匹配,发现不行。故4号点此时不能和7号点匹配,故判断一下能否和8号点匹配,发现8号点还没有匹配,故成功匹配上。 故左边所有节点匹配完毕,匹配数为4;

分析完过程,看看代码实现
练习链接 : 861. 二分图的最大匹配

#include<iostream>
#include<cstring>
using namespace std;
constexpr int N = 1e+5 + 10;
int n1, n2, m, e[N], ne[N], idx, g[N];// 为了便于找出节点相连的节点,采用邻接表的方式更方便
int match[N];// 用于标记右半部分的节点匹配的是左半部分那个节点    
bool st[N];  // 用于表示那个节点已经处于尝试匹配当中,或者就是表示该节点准备被匹配,其他已匹配到的节点另寻其他节点

auto add(int a, int b)
{
    e[idx] = b, ne[idx] = g[a], g[a] = idx++;   
}

auto find(int x) -> bool    // 寻找未被匹配的节点
{
    for(int i = g[x]; i != -1; i = ne[i])  // 依次遍历与自身节点相连的其他节点
    {
        int t = e[i];               
        if(st[t]) continue;    // 若该节点已被其他节点尝试匹配,则尝试下一节点
        st[t] = true;          // 标记右边的t节点为尝试匹配状态
        if(!match[t] || find(match[t]))  // 若此时右边的t节点未被匹配, 或者左边匹配到t的节点能换成另外一个节点则匹配成功
        {
            match[t] = x;      // 更新右边的t节点匹配左边的x节点
            return true;
        }
    }
    return false;
}

auto main() -> int
{
    cin >> n1 >> n2 >> m;
    memset(g, -1, sizeof g);
    while(m--)
    {
        int a, b; cin >> a >> b;
        add(a, b);
    }
    int res = 0;
    for(int i = 1; i <= n1; ++i)
    {
        memset(st, false, sizeof st);
        if(find(i)) res++;      // 匹配成功依次,则匹配数++
    } 
    cout << res << endl;

}