yukicoder No.368 LCM of K-products

問題はこちら
No.368 LCM of K-products - yukicoder

まずLCMについて考える
一般に、 $x_i=\displaystyle{\prod_j p_j^{e_{ij}}}$ と素因数分解される数に対して
$\displaystyle{LCM_{i\in I}x_i=\prod_j p_j^{max_{i\in I}(e_{ij})}}$ となる
ここで $\displaystyle{\prod_{i\in I}a_i=\prod_j p_j^{\sum_{i\in I}e_{ij}}}$ であることから求めるべきは
$\displaystyle{\prod_j p_j^{max_I\sum_{i\in I}e_{ij}}}$ となる。ただしmaxは#I=KとなるようなI全体を動く
$max_I\sum_{i\in I}e_{ij}$ は明らかに「 $e_{ij}$ の大きい方からK個の和」となるのでこれを求めれば良い

素数ごとに指数が大きいものからK個を取ってきて……と実装するのが意外とめんどくさい

d[3000][40];
//この配列のd[*][0]に素数を
//d[*][n+1]に、d[*][0]^nを因数に持つようなa[i]の個数を、それぞれ保存する
//10^9以下の数が1000個なので、そこに登場する素因数は高々3000個
//（最初の3000個の素数の積は10^9000より大きい）
//また2^30>10^9なので、その指数は30以下
ans,n,k,a,i,j,p,t,m=1e9+7;
long pow(a,n){return n?a*pow(a,n-1)%m:1;}
void push(p,t){
	//素数pを新たにdに追加する
	d[j][0]=p;
	d[j][1]=i;
	d[j][t+1]=1;
	j++;
}
int main(){
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%d",&a);
		for(j=0;d[j][0];j++){
			//既にdにある素数で割れるかどうかチェック
			for(t=0;a%d[j][0]<1;t++)a/=d[j][0];
			d[j][t+1]++;
		}
		if(a>1){
			//dにあるもの以外の素因数を探す
			for(p=2;a>=p*p;p++){
				for(t=0;a%p<1;t++)a/=p;
				if(t)push(p,t);
				//見つけたら追加
			}
			if(a>1)push(a,1);
		}
	}
	ans=1;
	for(i=0;d[i][0];i++){
		//各iごとに指数が大きな方からk個の和を求める
		p=t=0;
		for(j=30;t<k;){
			if(d[i][j]){
				d[i][j]--;
				t++;
				p+=j-1;
			}else j--;
		}
		ans=ans*pow(d[i][0],p)%m;
	}
	printf("%d",ans);
	return 0;
}

ひとまず短くする

d[3000][40];
x,n,i,j,k,t,m=1e9+7;
long p(a,n){return n?a*p(a,n-1)%m:1;}
f(s,t,y){
//素数sを探して、t番目をinc（見つからなければ末尾に追加する）
	for(y=0;d[++y][0]&&d[y][0]-s;);
	d[y][0]=s;
	d[y][t]++;
}
main(s){
	for(scanf("%*d%d",&n);~scanf("%d",&s);s>1&&f(s,1))for(k=1;s>=++k*k;t&&f(k,t))for(t=0;s%k<1;++t)s/=k;
	//sがk^tで割れるならf(k,t)としてdにデータを追加
	//f(s,0)のようなものをしないようにすることで、indexのずれを解消
	for(s=1;x=d[++i][0]?:!printf("%d",s);s=s*p(x,k)%m)for(k=t=0,j=30;t<n&&j;)d[i][j]--?t++,k+=j:--j;
}

頑張って短くする

d[3000][40];
x,n,i,j,k,t,m=1e9+7;
long p(a,n){return n?a*p(a,n-1)%m:1;}
f(s,x,y){
	for(t=y=0;d[++y][0]&&d[y][0]-s;);
	//グローバル変数tの初期化もここに紛れ込ませる
	d[y][0]=s;
	d[y][x]++;
}
main(s){
	for(scanf("%*d%d",&n);~scanf("%d",&s);f(s,1))for(k=2;s%k<1?s/=k,++t:(t&&f(k,t),s>k*k++););
	//s>1&&f(s,1)をやめた（1が入っても答えに影響しない）
	//また後ろのfor文を圧縮し、kをincするタイミングを変えることで1文字短縮
	for(s=1;x=d[++i][0]?:!printf("%d",s);s=s*p(x,k)%m)for(k=t=0,j=30;t<n&&d[i][j]--?t++,k+=j:--j;);
	//後ろのfor文を少しいじって短縮
}

326B

(2016/05/30追記)
ポインタを使えばもっと縮められた

d['~~'][40];
*q,n,i,k,t,m=1e9+7;
long p(a,n){return n?a*p(a,n-1)%m:1;}
f(s,x){
	for(q=d;*(q+=40)&&*q-s;);
	q[x]++;
	*q=s;
}
main(s){
	for(scanf("%*d%d",&n);~scanf("%d",&i);f(i,1))for(k=2;i%k<1?i/=k,++t:(t&&f(k,t),t=0,i>k*k++););
	for(q=d;*(q+=40);s=s*p(*q,k)%m)for(k=t=0,i=30;t<n&&q[i]--?t++,k+=i:--i;);
	i=!printf("%d",s);
}

307B

メモ

yukicoderでゆるふわgolf

yukicoder No.368 LCM of K-products