Codeforces #502 F. The Neutral Zone

うーん。
http://codeforces.com/contest/1017/problem/F

問題

logに似た関数を考える。

は関数fを用いて以下のように定義される。
のように素因数分解されたとすると、
となる。

整数Nとある３次関数f(x)が与えられる。
を求めよ。

なお、メモリは16MBしかない。

解法

各素数pに対し、1～Nの全要素を素因数分解した場合、pが素因数として登場する回数g(p)=N/p + N/(p^2)+ ...となる。
その場合、解にg(p) * f(p)だけ加算されることになる。
よって1～Nの範囲にある全素数pに対しg(p) * f(p)を求めればよいので、エラトステネスの篩ができればよい。
ただしメモリ容量がNより小さく、一般的なエラトステネスの篩を行うことができない。

この問題では、1～Nが素数かどうかだけ判定すればよいので、√N以下の素数を素因数に持つかだけわかればよい。
よって、エラトステネスの篩を√N毎に配列を使いまわしながら行うとよい。

unsigned int  N,A,B,C,D;
unsigned int ret=0;

const int prime_max = 0x10000;
int NP,prime[100000],divp[prime_max];
int NG[0x10000];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

unsigned int  F(unsigned int  x) {
	return (((A*x+B)*x+C)*x+D);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>C>>D;
	
	cprime();
	FOR(i,NP) {
		j=prime[i];
		for(x=j*2;x<0x10000;x+=j) NG[x]=1;
	}
	
	for(i=2;i<=N;i++) {
		if((i&0xFFFF)==0) {
			ZERO(NG);
			FOR(y,NP) {
				j=prime[y];
				for(x=(i+j-1)/j*j;x<i+0x10000;x+=j) NG[x&0xFFFF]=1;
			}
		}
		if(NG[i&0xFFFF]==0) {
			unsigned int num=N;
			unsigned int R=F(i);
			unsigned int pat=0;
			while(num>=i) pat+=num/i, num/=i;
			ret+=R*pat;
		}
		
	}
	cout<<ret<<endl;
}

まとめ

コメント欄で「これDiv2 CかDぐらいじゃない？」と言われてましたね…。