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

オイラープロジェクト91~100 - (2012/08/27 (月) 15:57:16) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*問い92
+各桁の2乗を足し合わせた数を求め、それを繰りかすと必ず1か89に到達する。
+1000万以下で89に到達する数の個数を求めよ。
+
+
+ #include<stdio.h>
+ int memo[1000]={0};
+ int saiki(int n){
+	if(n==1||n==89){
+		return n;
+	}
+	if(n<1000&&memo[n]!=0)return memo[n];
+	int next=0,m=n;
+	while(m!=0){
+		next+=(m%10)*(m%10);
+		m/=10;
+	}
+	m=saiki(next);
+	if(n<1000)memo[n]=m;
+	return m;
+ }
+ int main(){
+	int ans=0;
+	for(int i=1;i<10000000;i++){
+		ans+=(saiki(i)==89);
+	}
+	printf("%d",ans);
+ }
+
+
+
 *問い97
 28433×2^7830457+1は素数でありこれの下10ケタを答えよという問題。
 Lispは苦手だけどLispでなかったらこんなに簡潔には書けない気もする。
 Lisp様様って感じ(俺がヘボいだけかな)
 
 
 
  (defvar mask 10000000000)
  mask
  (setq mask 10000000000)
  10000000000
  (defun saiki (n m all)
    (if (< 0 m)
        (if (= (mod m 2) 1) 
  	  (saiki (mod (* n n) mask) (floor (/ m 2)) (mod (* all n) mask))
  	(saiki (mod (* n n) mask) (floor (/ m 2)) all))
      all))
  saiki
  (mod (+ (* (saiki 2 7830457 1)  28433) 1) mask)