题解 CF776B 【Sherlock and his girlfriend】

发表于 | 更新于 | 阅读次数：
本文字数： 2.8k | 阅读时长 ≈ 3 分钟

前言

题目翻译有问题

Watson给Sherlock一个挑战：给这些珠宝首饰上色，当一件的价格是另一间的价格的因子时，使得这两件两件没有相同的颜色。此外，Watson要求他使用的尽量少种颜色。

其实应该是

Watson给Sherlock一个挑战：给这些珠宝首饰上色，当一件的价格是另一件的价格的质因子时，使得这两件首饰没有相同的颜色。此外，Watson要求他尽量使用少种颜色。

(错别字看着难受)

正题

分析题目

我们看一下数据大小 (标签)，$1<=n<=100000$，这不是可以写暴力吗？

我们可以现在手动模拟一下

在理解一下题意并手动模拟一下后，不难发现只有在$n<3$时颜色数为$1$，其余情况颜色数均为$2$(惊不惊喜，意不意外)。

快乐的分析代码时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#pragma GCC optimize(3)//O3优化
#include<bits/stdc++.h>
#define ll long long

using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
template < class T > inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    x = f ? -x : x;
}
#undef getchar()

template < class T > inline void write(T x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}//输入输出优化

const ll FFF=1000000+5;

ll n;
ll ans=1;

struct node
{
    ll price,color;
}zb[FFF];//price表示珠宝的价格，color表示珠宝的颜色
//zb表示珠宝(拼音应该看得懂吧)

bool isprime(int x){
    if(x==1)
        return false;
    if(x==2||x==3)
        return true;
    if(x%6!=1&&x%6!=5)
        return false;
    int s=sqrt(x);
    for(int i=5;i<=s;i+=6)
        if(x%i==0||x%(i+2)==0)
            return false;
    return true;
}//(龟速)判断素数(想要快一点的话可以去学一学埃氏筛，MR等等快一点的筛法)

int main()
{
    if(fopen("aaa.in", "r"))
    {
        freopen("aaa.in", "r", stdin);
        freopen("aaa.out", "w", stdout);
    }
    ios::sync_with_stdio(false);//关闭流同步，还是输入输出优化
    read(n);
    for(int i=1;i<=n;++i)
    {
        zb[i].price=i+1;
        zb[i].color=1;
    }//初始化，定义珠宝i的价格为i+1,颜色为1
    for(int i=1;i<=n/2;++i)//只需要从1搜索到n/2，因为n/2+1到n这个区间中是不可能互相为质因子的
    {
        if(isprime(zb[i].price)==true)//如果i是质数，那它可能是作为某一个数的质因子
        {
            ll now=1;//现在进行枚举，枚举一个数的质因子为zb[i].price，now表示倍数
            while(now*zb[i].price<=n+1)//如果枚举的数不大于n(即价格不大于n+1)，就说明zb[i].price是这个数的质因数
            {
                now+=1;//倍数+=1，
                zb[now*zb[i].price-1].color=zb[i].color==1?2:1;//zb[now*zb[i].price-1].color要与zb[i].color不同，所以当zb[i].color==1时zb[now*zb[i].price-1].color=2.否则zb[now*zb[i].price-1].color=1
            }
        }
    }
    write(n<3?1:2);//根据上面的结论，当n<3时输出1，否则输出2
    putchar('\n');
    for(int i=1;i<=n;++i)
    {
        write(zb[i].color);//输出第i个珠宝的颜色
        putchar(' ');
    }
    return 0;
}