yukicoder No.144 エラトステネスのざる

問題はこちら
No.144 エラトステネスのざる - yukicoder

問題文中で「下線部の処理」とされている部分のことを、以下「消去」と呼ぶ
kが素数と判定される確率をf(k)とおくと期待値の線形性からΣf(k)が求める答えとなるのでf(k)を求めることを考える
kがリストから消されるのは、kのいずれかの約数で「消去」が実行された時。
よってkが素数と判定されるためには、kの任意の約数について
候補リストから素数リストに移動される際に「消去」が実行されないことが必要十分
ここでkについての（あるいはkの約数の個数についての）数学的帰納法により、これは
kの全ての約数が素数と判定され、かつ、候補リストから素数リストに移動される際に「消去」が実行されないことが必要十分
よって結局求める確率は、(1-p)^(σ0(k)-2)となる
（σ0は約数関数。1とk自身を除くので2を引いている）

N以下のすべての数について逐一約数の個数を求めていたら間に合わないので実装は少し考える

main(){
	double s,p;
	int n,i,j,x[1<<20]={};
	//kの約数の個数をx[k]に保存
	scanf("%d%lf",&n,&p);
	for(i=1;i<=n;i++)for(j=i;j<=n;j+=i)x[j]++;
	//jはiを約数に持つのでx[j]をinc
	for(;n>1;n--)s+=pow(1-p,x[n]-2);
	printf("%f",s);
	return 0;
}

ささっと縮める

double s,p;
n,j,x[2<<20];
main(i){
	for(scanf("%d%lf",&n,&p);++i<n;)for(j=i;j<n;x[j+=i]++);
	for(;n>1;s+=pow(1-p,x[n--]));
	j=!printf("%f",s);
}

出力部分のn>1が邪魔なのでxのindexを1つずらす

for(scanf("%d%lf",&n,&p);++i<n;)for(j=i-1;j<n;x[j+=i]++);
for(;--n;s+=pow(1-p,x[n]));

for文圧縮

//1つ目
for(scanf("%d%lf",&n,&p);++i<n;)for(j=i-1;j<n;x[j+=i]++);
//形式的書き換え
for(scanf("%d%lf",&n,&p);j<n?++x[j+=i]:(j=i++)<n;);
//事前にi=2,j=1をセットしておく必要があることに注意

//2つ目
for(scanf("%d%lf",&n,&p);j<n?++x[j+=i]:(j=i++)<n;);for(;--n;s+=pow(1-p,x[n]));
//形式的書き換え
for(scanf("%d%lf",&n,&p);j<n?++x[j+=i]:(j=i++)>n?s+=pow(1-p,x[--n]),n:1;);
//pow(1-p,x[0])が実行されるので、sが余分に1大きくなることに注意
//（pow(0,0)は1がかえってくる）

以上より

double s,p;
n,i=2,x[2<<20];
main(j){
	for(scanf("%d%lf",&n,&p);j<n?++x[j+=i]:(j=i++)>n?s+=pow(1-p,x[--n]),n:1;);
	i=!printf("%f",s-1);
}

129B

2017/01/14追記
for文圧縮をする前のコードを一旦再掲

double s,p;
n,j,x[2<<20];
main(i){
	for(scanf("%d%lf",&n,&p);++i<n;)for(j=i;j<n;x[j+=i]++);
	for(;n>1;s+=pow(1-p,x[n--]));
	j=!printf("%f",s);
}

一度i>mとなれば、それ以降x[m]の値を変更することはないので、pow(1-p,x[*])を足していく操作は、1つ目のfor文にまとめてしまう事ができる
x[n]の値が足されるように、ループの終了条件に注意して

double s,p;
n,j,x[2<<20];
main(i){
	for(scanf("%d%lf",&n,&p);n/++i;s+=pow(1-p,x[i]))for(j=i;j<n;x[j+=i]++);
	j=!printf("%f",s);
}

ループ圧縮をし、indexをぐっと睨むと、次のようにまとめられる

double s,p;
n,j,x[2<<20];
main(i){
	for(scanf("%d%lf",&n,&p);j>n?s+=pow(1-p,x[++i]-1),j=i%n:++x[j+=i];);
	j=!printf("%f",s);
}

iが1のときからループが始まるのでx[*]に保存される値は1大きくなる
それが終わるとsにはx[2]が加えられるので、ループの終了条件は再びi<nで良くなる
119B

2017/06/18追記
xに保存する値を正負逆にすることで1B、gccのバージョンアップでmainの返り値が不問になったことで3Bの計4B短縮

double s,p;
n,j,x[2<<20];
main(i){
	for(scanf("%d%lf",&n,&p);j>n?s+=pow(1-p,~x[++i]),j=i%n:--x[j+=i];);
	printf("%f",s);
}

115B