yukicoder : No.2545 Divide by 3

なるほど。
https://yukicoder.me/problems/no/2545

問題

100個の番地があるメモリがあり、初期状態で1番には正整数X、2番には1、それ以外には0が入っている。
以下の手順を繰り返し、Xが10^9以下のどんな整数であれ、3番にfloor(X/3)が入る一連の手順を求めよ。

• 2つの番地の合計を指定した番地に格納する
• 指定した番地の値を2で割った値を、指定した番地に格納する

解法

1/3=1/4+1/(4^2)+1/(4^3)+....
であることを用いる。
固定小数点の考え方で計算しよう。

すなわち(2^32)*(X+1)に対し、1/4, 1/(4^2), 1/(4^3)....を掛けたものの和を取り、最後に2^32で割ればよい。
この処理は加算と2での除算のみで計算できる。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	// (X+1)^(2^32)を作成
	cout<<(32+16*3+1)<<endl;
	cout<<"plus 4 1 2"<<endl;
	FOR(i,16) {
		cout<<"plus 3 4 3"<<endl;
		cout<<"plus 4 4 4"<<endl;
		cout<<"plus 4 4 4"<<endl;
	}
	FOR(i,32) {
		cout<<"div 3 3"<<endl;
	}

	
}

まとめ

意外に短く書けるもんだ。