yukicoder : No.1567 Integer Coefficient Equation

これは数学問。
https://yukicoder.me/problems/no/1567

問題

整数P,L,Rが与えられる。
整数係数多項式f(x)のうち、f(x)=Pの異なる整数解が5個以上あり、かつL≦k≦Rに対しf(x)=kが整数解をもつものは何通りか。

解法

f'(x)=f(x)-Pとすると、f'(x)=0が5個以上整数解をもち、f'(x)=k-Pが整数解を持つ、と言い換えることができる。

5個の解をa,b,c,d,eとするとf'(x)=g(x)(x-a)(x-b)(x-c)(x-d)(x-e)と置いた時、f'(x)=k-Pが整数解を持つ条件はa*b*c*d*eがk-Pの約数であることである。

そこで、L-P以上R-L以下の整数のうち、5個以上の約数の積に分解できるものを列挙しよう。
素因数が3個以上あるとき、それらをx,y,zとすると、1,-1,x,y,zが解の候補となる。
ただし素因数がちょうど3個しかなく、x=y=zの場合、どうしてもどこかが一致してしまい不可である。

そこで、前処理として各正整数に対し、素因数が何個あるか、また素因数がちょうど3個の時それらが一致しない(=素数の3乗でない)かを求めておき、累積和を取っておこう。

int T;

int C[402020];
int S[402020];
vector<int> V[402020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=2;i<=400000;i++) C[i]=i;
	for(i=2;i<=400000;i++) {
		if(C[i]==i) {
			for(j=i;j<=400000;j+=i) {
				while(C[j]%i==0) {
					V[j].push_back(i);
					C[j]/=i;
				}
			}
		}
		x=0;
		if(V[i].size()>3||(V[i].size()==3&&V[i][0]!=V[i][2])) x=1;
		S[i]=S[i-1]+x;
	}
	
	
	
	cin>>T;
	while(T--) {
		int P,L,R;
		cin>>P>>L>>R;
		L-=P;
		R-=P;
		int ret=0;
		if(L>0) ret+=S[R]-S[L-1];
		else if(L==0) ret+=S[R]+1;
		else if(R>=0) ret+=S[R]+1+S[-L];
		else ret=S[-L]-S[-R-1];
		cout<<ret<<endl;
	}
}

まとめ

うーむ。