※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「オイラープロジェクト121~130」の編集履歴(バックアップ)一覧に戻る

オイラープロジェクト121~130 - (2012/09/10 (月) 16:24:07) の編集履歴(バックアップ)


問い121

袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.
プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.
ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう. 支払いはすべてポンドの整数倍であり, またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため, 与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.
15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.
解法
組み合わせ数が少ないのでLispの分数計算で全探索します。

(defun saiki (p deep get)
  (if (= deep 15)
      (if (< (/ deep 2) get) p 0)
    (+ (saiki (* p (/ 1 (+ deep 2))) (+ deep 1) (+ get 1))
       (saiki (* p (/ (+ deep 1) (+ deep 2))) (+ deep 1) get))))
saiki
(let ((a (saiki 1 0 0)) (b 0) (c 0))
  (setq b (numerator a)
	c (denominator a))
  (floor (/ c b)))



問い123

pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)n + (pn + 1)n を pn2 で割った余りとする.
例えば, n = 3 のとき, p3 = 5 であり, 43 + 63 = 280 ≡ 5 mod 25.
余り r が 109 より大きくなる n の最小値は 7037 である.
余り r が 1010 より大きくなる最初の n を求めよ.

モード演算は分けて個別に計算しても全部合わせて計算しても答えが変わらないということを利用してステップ単位で解きます。

高速化しようと考え
n^23=n^16*n^4*n^2*n^1のように累乗が2^累乗の指数に分解出来る性質を利用して解こうとしたらint64で溢れるので上手くいきません。
Lispなら高速化は簡単ですがC++では多倍張整数を用意しないと無理かもしれません。




#include<stdio.h>
#include<vector>
#include<iostream>
const int up=1000000;
std::vector<__int64> sosuu; 
bool so[up];
void setSo(){
int i2;
memset(so,true,sizeof(so));
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
	if(so[i]==false)continue;
	sosuu.push_back(i);
	i2=i*2;
	for(int j=i*3;j<up;j+=i2){
		so[j]=false;
	}
}
}
int main(){
setSo();
__int64 p,pd,pu,p2,calcD,calcU,ten=1;
for(int i=0;i<10;i++){
	ten*=10;
}
for(int i=0;i<sosuu.size();i++){
	p=sosuu[i];
	p2=p*p;
	calcD=pd=p-1;
	calcU=pu=p+1;
	for(int n=0;n<i;n++){
		calcD=(calcD*pd)%p2;
		calcU=(calcU*pu)%p2;
	}
	//std::cout<<(calcD+calcU)%p2<<"\n";
	if((calcU+calcD)%p2>ten){
		std::cout<<i+1;
		break;
	}
}
std::cout<<"?";
}