KUPC 2011 E: Fox Number

その他のコンテスト

問題概要

正整数Nで、N = Π p[i]^e[i], p[i]:素数, p[i] < p[i+1], e[i] >= e[i+1]を満たすようなものをFox Numberという。A(<10^12)、B(<5*10^5)が与えられるとき、[A-B, A+B]に存在するFox Numberの個数を求める問題。

考えたこと

  • とりあえず、A-Bが負になったり1がFox Numberでないとかには気をつけとこう。
  • 一目、区間篩っぽいのが見えるけど。
  • とりあえず因数分解した結果を知っていれば判定はlog xくらいでできる。
  • Pollard rhoで素因数分解したら期待計算量O(N^1/4 * polylog(N))くらいなので一応L(区間の長さ、<10^6)* 10^3 * polylogくらいでぎりぎり間に合いそうとも言えるしpolylogで死にそうな気もする。今回は見送ろう。
  • mapで素因数分解した結果を持っておいて、小手先の高速化しても全然最大ケースが終わらない。
  • コンテスト終了後テスターのいもす先生に聞いたら、普通にやれば通る、ということだった。mapの重さとか枝刈りのセンスの無さが問題だったらしい。
  • 終了後、区間篩っぽい方法で通した。これは通しておくべきだったなあ。
  • Fox Numberの性質は枝刈り(Fox Numberでないことの判定)を容易にするための、しえるさんの優しさだと思っておく。

終了後通したコード

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long int64;

int64 A, B;
const int INF = 1<<29;
const int NOT_FOX = -1;

const int MAX_SIZE = 2000000;
bool isPrime[MAX_SIZE];
int div_num_instance[1200000];
int *div_num;

void seive(){
	memset(isPrime, -1, sizeof(isPrime));
	bool *ps = isPrime;
	ps[0] = ps[1] = false;
	for(int i=2; i*i<MAX_SIZE; i++)if(ps[i]){
		for(int j=i<<1; j<MAX_SIZE; j+=i){
			ps[j] = false;
		}
	}
}

//区間篩, 割り切る最小の素数も覚えておく
//[from, to)
int solve(int64 from, int64 to){

	fill(div_num + from, div_num + to, INF);

	for(int i=2; i<MAX_SIZE; i++)if(isPrime[i]){
		for(int64 j=max(2LL*i, (from+i-1)/i*i); j < to; j += i)if(div_num[j] != NOT_FOX){
			int64 t = j;
			int div_count = 0;
			while(t % i == 0){
				t /= i;
				div_count++;
			}
			if(div_count > div_num[j]){
				div_num[j] = NOT_FOX;
			}
			else{
				div_num[j] = div_count;
			}
		}
	}

	return (int)( to - from - count(div_num + from, div_num + to, NOT_FOX));
}


int main(){

	scanf("%lld%lld",&A, &B);

	div_num = div_num_instance - (A-B);

	//素因数分解
	seive();

	//本体
	printf("%d\n", solve(max(2LL, A-B), A+B+1));

	return 0;
}