TopCoder SRM 811 : Div1 Medium SmoothDivisors

エイヤでやってしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=17132&rd=18802

問題

ある整数集合Sがsmoothであるとは、その要素を並べた数列のうち、隣接要素(および両端)のGCDが2以上になるように並べられるものをいう。
A以上B以下の整数Xのうち、1とX以外のXの約数からなる集合がsmoothであるものはいくつか。

解法

多次元のグリッドにおける巡回路を考えてみると、Xを素因数分解したとき、X=pqまたはX=pq^2の形におけるものはsmoothでない。
そこで、エラトステネスの要領で、A以上B以下の各値について、素因数の種類とその次数を数え上げよう。
Bの上限がかなり大きいので、除算などは避け極力定数倍高速化を行っておいた方が良い。

const int N=40000000;
char num[N+4];
char sum[N+4];

class SmoothDivisors {
	public:
	int count(int A, int B) {
		int i,j;
		ZERO(num);
		ZERO(sum);
		for(i=2;i<=N;i++) if(num[i]==0) {
			for(j=i;j<=N;j+=i) {
				num[j]++;
				sum[j]++;
			}
			for(ll cur=1LL*i*i;cur<=N;cur*=i) {
				for(j=cur;j<=N;j+=cur) sum[j]++;
			}
		}
		
		int ret=0;
		for(i=A;i<=B;i++) {
			ret++;
			if(num[i]==2&&sum[i]==2) ret--;
			if(num[i]==2&&sum[i]==3) ret--;
		}
		return ret;
		
	}
}

まとめ

X=pqr、X=pq^3、X=p^2q^2の形をとる場合、smoothにできることを確認したけど、それ以外一般的にsmoothかどうかは未確認のまま投げてしまった…。