2022.1.28 训练日记 4.AcWing 1293. 夏洛克和他的girlfriend_综合

题目链接：夏洛克和他的女朋友

题目分析：

 0.这是一道筛质数 + 二分图思想的题目。1.通过题目分析，我们可以得出来一个特点：如果要连线（产生这种关系）的话，都是从一个质数连向一个合数。2.因此，我们可以把本题类比于一个二分图。左边集合是质数，右边集合是合数。如果a是b的质因数，则连一条a->b的边。因为集合内部的颜色没有限制。所以最多用两种颜色。质数集合用一种，合数集合用一种。3.当n == 1 时 价值为 2 故只需要1种颜色。当n == 2 时 价值为 2，3 两个都是质数 故只需要一种颜色。当n == 3 时 价值为 2，3，4 有一个合数。故需要两种颜色。我们可以发现，只要有合数就一定需要两种。因为每个合数都有质因数，故只要存在合数必定有一条连向它的边。

code:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int primes[N], cnt;
bool st[N];void init(int n)
{
    for(int i = 2; i <= n; i ++){
    if(!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] <= n / i; j ++){
    st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}
int main()
{
    init(N);int n;cin >> n;//需要用到的颜色种类if(n <= 2) puts("1");else puts("2");//从2枚举到n+1 或者 1到n if(!st[i + 1])for(int i = 2; i <= n + 1; i ++){
    if(!st[i + 1]) printf("1 ");else printf("2 ");}return 0;
}

总结：

1.注意边界
2.质数定理：1~n中的质数个数为 n/ln n。
3.二分图：如果一张无向图的N个节点(N>=2)可以分成A,B两个非空集合。其中A和B的交集是空集，并且在同一集合内的点之间都没有边相连，那么称这张无向图为二分图，A,B为二分图的左部和右部。