PKU3406

今日もodzさんのところから問題ゲット(id:odz:20080113)。
ただ、他の人と比べてメモリの使用量がすんごい事になってる。
ううむ、なんか、実装に大分差がありそうだなー。
問題がだるい大きさなのでコードサイズの削減がかなーり適当です。
たぶん、普通にまだ削れる気がする。

1の位の頻度表作って計算するだけー
エラトステネス君がメモリ食いすぎー

#import<algo.h>
long long n,r,x=1,y,p['___'],t[9];
main(){
	for(cin>>n>>r;x++<n;){
		for(y=x;!p[x]&y<=n;)p[y+=x]=1;
		for(y=x;!p[x]&y<=n;y*=x)t[x%10]+=n/y-(n-r)/y-r/y;
	}
	t[2]-=x=t[2]<?t[5];
	t[5]-=x;
	for(r=n=1;n++<9;)
		for(y=t[x=n]&3;y%2?r=r*x%10:y;y/=2)
			x*=x;
	cout<<r<<"\n";
}

こっそり追記：
<<"\n"とか必要ないだろ常考。
あとg++のalgorithmにはpowerあったよなぁとか記憶から引きずり出してきた。

#import<algo.h>
long long n,r,x=1,y,p['___'],t[9];
main(){
	for(cin>>n>>r;x++<n;){
		for(y=x;!p[x]*n/y;)
			p[y+=x]=1;
		for(y=x;!p[x]*n/y;y*=x)
			t[x%10]+=n/y-(n-r)/y-r/y;
	}
	t[2]-=x=t[2]<?t[5];
	t[5]-=x;
	for(r=n=1;n++<9;)
		r*=power(n,t[n]&3);
	cout<<r%10;
}