题目大意

给定 $n$ 个点，两点之间有一条从编号小的点到编号大的点有向边，要求给这些边染上三种颜色，使得不存在一条长度超过 $3$ 的相同颜色的路径。

简单分析

首先可以注意到题目中的数字 $3$，为什么出题人要用 $3$ 这个数字而非 $2$ 呢？其实这个数字用得很妙。那么接下来请看笔者娓娓道来。

如果我们把所有边都染成一个颜色，由于 $x_i$ 的最大值不超过 $10^{18}$，那么可以发现从一个点开始，每走一步至少会乘 $2$，最多可以一口气走 $60$ 步，然后就不能走了。

我们不妨将这 $60$ 步形成的链提出来，然后将前 $20$ 步染成颜色 $1$，中间 $20$ 步染成颜色 $2$，最后 $20$ 步染成颜色 $3$，这样我们就有了 $0$ 分的成绩。

那我们也许可以将第 $i$ 步染成 $i\bmod 3+1$ ，但是实际上这条链并非与其他边没有关系，我们如果只考虑两者之间的相对关系，是可能影响正确性的。

考虑一个数的 $60$ 个二进制位，将其分块，每 $4$ 位分为一个小块，每 $4$ 小块分为一个大块，最后会分出 $4$ 个大块。可以将同一小块内的点两两连边染成颜色 $1$，同一大块内不同小块的点两两连边染成颜色 $2$，剩下的边染成颜色 $3$，这样做为什么是正确的呢？考虑从一个点开始走，如果要走三条相同颜色的边，那么第四步一定会走一条不同颜色的边。

#include<iostream>
#include<cstdio>

using namespace std;
typedef long long ll;
const int N=1005;

int n;
ll a[N],val[N];
int color(int x,int y){
	if(x/4==y/4)return 1;
	else if(x/16==y/16)return 2;
	else return 3;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	for(int i=1;i<=n;i++)val[i]=63-__builtin_clzll(a[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]%a[j]==0)printf("%d%c",color(val[i],val[j])," \n"[j==i-1]);
			else printf("%d%c",rand()%3+1," \n"[j==i-1]);
		}
	}
	return 0;
}