洛谷 CF776B & LOJ 10201 -「一本通 6.2 练习 4」Sherlock and His Girlfriend

题面

题目传送门

Sherlock 有了一个新女友(这太不像他了!)。情人节到了,他想送给女友一些珠宝当做礼物。

他买了 $n$ 件珠宝。第 $i$ 件的价值是 $i+1$ 。那就是说,珠宝的价值分别为 $2,3,4,.. ,n+1$ 。

Watson 挑战 Sherlock,让他给这些珠宝染色,使得一件珠宝的价格是另一件的质因子时,两件珠宝的颜色不同。并且,Watson 要求他最小化颜色的使用数。

请帮助 Sherlock 完成这个简单的任务。

输入格式

只有一行一个整数 $n$,表示珠宝件数。

输出格式

第一行一个整数 $k$,表示最少的染色数;
第二行 $n$ 个整数,表示第 $1$ 到第 $n$ 件珠宝被染成的颜色。若有多种答案,输出任意一种。

思路

对于这一段区间内的所有合数,他们一定不互为质因子(都不是质数了当然不互为质因子),所以只需要把区间内的质数全部染上一种颜色,合数染上另一种颜色,只需 2 种颜色。

注意:当 $n<=2$ 时,只需要一种颜色,所以要特判。

代码

#include<bits/stdc++.h>
using namespace std;
int pr[1000005]={2};
long long top=0;
int is[1000005];
int n;
void prime_oulashai(){
    top=1;
    for (int i=2;i<=1000000;i++){
        if (!is[i]){
            pr[top++]=i;
        }
        for (int j=0;j<=top-1;j++){
            if (i*pr[j]>1000000){
                break;
            }
            is[i*pr[j]]=1;
            if (i%pr[j]==0){
                break;
            }
        }
    }
}
int main(){
	cin>>n;
	if (n==1){
		cout<<"1\n1";
		return 0;
	}
	if (n==2){
		cout<<"1\n1 1";
		return 0;
	}
	prime_oulashai();
	is[2]=0;
	cout<<2<<endl;
	for (int i=1;i<=n;i++){
		if (is[i+1]){
			cout<<1<<" ";
		}else{
			cout<<2<<" ";
		}
	}
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇
下一篇