問題はこちら
No.435 占い(Extra) - yukicoder
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
2017/06/19追記
fのreturn文省略で2B、pの正負反転で1Bの計3B短縮
y,i,t,a,b,m,s,c,p,x,g; f(n){g=!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?!p:3), p-=f(n),c*=y, p+=f(++i),c=c*y*y*y*y*y%9; }
242B