yukicoder : No.1653 Squarefree

★3とはいえこちらはさほど難しくない。
https://yukicoder.me/problems/no/1653

問題

正整数がsquarefreeであるとは、2以上のいかなる平方数でも割り切れないことを意味する。
2整数L,Rが与えられる。L以上R以下の整数のうち、squarefreeなものは何通りか。

なお、Rの上限は10^18と大きいが、LとRの差は10^6以下である。

解法

L,Rは大きいがR-Lは小さい。
そこで、L～Rを持つ整数列を作り、各要素に対しエラトステネスの篩の要領で素因数2～(10^6)で割れるだけ割ってみよう。
同じ素因数で2回以上割れる整数は、当然squarefreeでない。

Rの上限は10^18なので、10^6までの素因数で割っても2以上の数値は、平方数が素数であるかのいずれかである。
そこでそれぞれ平方数かどうか判定すればよい。

ll L,R;
int N;
ll C[1010101];
int did[1010101];

ll issq(ll V) {
	ll a=sqrt(V);
	for(ll b=a-2;b<=a+2;b++) if(b*b==V) return 1;
	return 0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>R;
	R++;
	N=R-L;
	FOR(i,N) C[i]=L+i;
	for(i=2;i<=1000000;i++) {
		ll s=(L+(i-1))/i*i;
		for(x=s-L;x<N;x+=i) {
			int num=0;
			while(C[x]%i==0) {
				num++;
				C[x]/=i;
			}
			if(num>=2) did[x]++;
		}
	}
	int ret=0;
	FOR(i,N) {
		if(did[i] || (C[i]>1&&issq(C[i]))) ret++;
	}
	cout<<N-ret<<endl;
}

まとめ

この前の問題よりはとっつきやすいよね。