読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.435 占い(Extra)

問題はこちら
No.435 占い(Extra) - yukicoder

yukicoder No.434 占い - メモと全く同じ

x,a,b,m,n,i,t,ans,c,c3;
inv9[]={0,1,5,0,7,2,0,4,8};
f3(n){int i=0;for(;n&&n%3==0;n/=3)i++;return i;}
g3(n){for(;n&&n%3==0;n/=3);return n;}
main(){
	for(gets(&i);~scanf("%d%d%d%d%d",&n,&x,&a,&b,&m);){
		n--;
		t=ans=c3=0,c=1;
		for(i=0;i<=n;i++){
			t+=x%10;
			ans+=c*(c3?c3==1?3:0:1)*(x%10)%9;
			c3+=f3(n-i)-f3(i+1);
			c=c*g3(n-i)*inv9[g3(i+1)%9]%9;
			x=((x^a)+b)%m;
		}
		printf("%d\n",ans%9?:t?9:0);
	}
	return 0;
}

434をそのまま使いまわす……つもりが変数名がかぶりまくっててつらい

y,i,t,a,b,m,s,c,p,x;
v[]={0,1,5,0,7,2,0,4,8};
f(n){return!n|n%3?y=n,0:f(n/3)+1;}
main(n){
	for(gets(&c);y=~scanf("%d%d%d%d%d",&n,&x,&a,&b,&m);t=s=p=i=!printf("%d\n",s%9?:t?9:0)){
		for(c=1;n--;x=((x^a)+b)%m){
			t+=x%10;
			s+=c*(p-1?!p:3)*(x%10)%9;
			p+=f(n);c*=y;
			p-=f(++i);c=c*v[y%9]%9;
		}
	}
}

272B

2016/10/23追記
434と全く同じ理由で19B削減

y,i,t,a,b,m,s,c,p,x;
f(n){return!n|n%3?y=n%9,0:f(n/3)+1;}
main(n){
	for(gets(&c);y=~scanf("%d%d%d%d%d",&n,&x,&a,&b,&m);t=s=p=i=!printf("%d\n",s%9?:t?9:0)){
		for(c=1;n--;x=((x^a)+b)%m){
			t+=x%10;
			s+=c*(p-1?!p:3)*(x%10)%9;
			p+=f(n);c*=y;
			p-=f(++i);c=c*y*y*y*y*y%9;
		}
	}
}

253B

2016/11/03追記
for文に{}を使ってるとか馬鹿なの?死ぬの?

y,i,t,a,b,m,s,c,p,x;
f(n){return!n|n%3?y=n%9,0:f(n/3)+1;}
main(n){
	for(gets(&c);y=~scanf("%d%d%d%d%d",&n,&x,&a,&b,&m);t=s=p=i=!printf("%d\n",s%9?:t?9:0))
		for(c=1;n--;x=((x^a)+b)%m)
			t+=x%10,
			s+=c*(p-1?!p:3)*(x%10)%9,
			p+=f(n),c*=y,
			p-=f(++i),c=c*y*y*y*y*y%9;
}

249B


2016/12/19追記
・x%10を前に持っていくことでカッコを外すことが出来る
・sに加算する値は1回につき高々8*3*9=216、ループ回数は|S|≦10^7
……これだけだと符号付き32bitの上限2^31-1=2147483647で押さえられないが、多分もう少し厳しい上界を持ってくればオーバーフローしないことがいえるはず。
なので毎回剰余を取る必要はない

y,i,t,a,b,m,s,c,p,x;
f(n){return!n|n%3?y=n%9,0:f(n/3)+1;}
main(n){
	for(gets(&c);y=~scanf("%d%d%d%d%d",&n,&x,&a,&b,&m);t=s=p=i=!printf("%d\n",s%9?:t?9:0))
		for(c=1;n--;x=((x^a)+b)%m)
			t+=x%10,
			s+=x%10*c*(p-1?!p:3),
			p+=f(n),c*=y,
			p-=f(++i),c=c*y*y*y*y*y%9;
}

245B