「プロジェクトオイラー問い91~100」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問い91~100」(2013/01/04 (金) 04:52:52) の最新版変更点

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

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

*問い91 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2091 0<=x,y<=50の格子点で直角三角形を作るとき点の一つを原点に固定した時何通りの三角形を作れるか? 解法 直角になる地点が決まれば後はベクトルの直角の概念から条件を満たす残りの点は決まります。 それを素直に計算するだけです。 #include<stdio.h> #include<algorithm> int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } int main(){ int ans=0; for(int ax=0;ax<=50;ax++){ for(int ay=0;ay<=50;ay++){ if(ax==0&&ay==0){ ans+=50*50; }else if(ax==0||ay==0){ ans+=50; }else{ int k=gcd(ax,ay); ans+=std::min((50-ay)/(ax/k),ax/(ay/k));//左上 ans+=std::min(ay/(ax/k),(50-ax)/(ay/k)); } } } printf("%d",ans); } *問い92 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2092 各桁の2乗を足し合わせて新たな数を作ることを, 同じ数が現れるまで繰り返す. 例えば   44 → 32 → 13 → 10 → 1 → 1   85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 のような列である. どちらも1か89で無限ループに陥っている. 驚くことに, どの数から始めても最終的に1か89に到達する. では, 10,000,000より小さい数で89に到達する数はいくつあるか. 解法 1000万までの数は各桁の2乗和を取ると確実に1000以下の数となるのでここまでの数を最初にメモ化して計算すれば十分です。 逆関数で89からチェーンを逆にたどればコードは少し早くなるかもしれません。 #include<stdio.h> int facter[10]={0,1,4,9,16,25,36,49,64,81}; const up=1000; int memo[up+1]={0}; int next(int n){ int re=0; while(n!=0){ re+=facter[n%10]; n/=10; } return re; } int main(){ int ans=0,num; for(int i=2;i<=up;i++){ num=i; while(num!=89&&num!=1)num=next(num); if(num==89){ ans++; memo[i]=1; } } for(int i=1000;i<1000*10000;i++){ ans+=memo[next(i)]; } printf("%d",ans); } *問い95 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2095 ある数の真の約数とは, それ自身を除く約数すべてである. 例えば, 28 の真の約数は 1, 2, 4, 7, 14 である. これらの約数の和は 28 に等しいため, これを完全数と呼ぶ. 面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており, 二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる. さらに長い鎖はあまり知られていないだろう. 例えば, 12496 から始めると, 5 つの数の鎖をなす. 12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...) この鎖は出発点に戻っているため, 友愛鎖と呼ばれる. いずれの要素も 1,000,000 を超えない最長の友愛鎖の最小のメンバーを求めよ. 解法 この問題をグラフにするとループとループに入る木構造、もしくは100万以上になってループが途絶える木構造の2種類になります。 一番長いループを探す問題なのですが、賢い方法も思いつかなかったので全部の鎖をチェックしてます。 #include<stdio.h> const int up=1000*1000; int memo[up+1]={0}; int calc(int n){ __int64 re=1; int t=n; for(int i=2;i*i<=n;i+=(i&1)+1){ int mul=1; while(n%i==0){ mul*=i; n/=i; } if(mul!=1){ re*=(mul*i-1)/(i-1); } } if(n!=1)re*=(n+1); return re-t; } int saiki(int s,int n){ if(n>=up){ return -up; } if(s==n)return 1; if(memo[n]==1)return -up; memo[n]=1; int t=saiki(s,calc(n))+1; memo[n]=0; return t; } int main(){ int ansLen=0,ans; for(int i=1;i<up;i++){ int len=saiki(i,calc(i)); if(len>ansLen){ ansLen=len; ans=i; } } printf("%d %d",ans,ansLen); } *問い97 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2097 非メルセンヌ素数 28433×2^7830457+1 の末尾10桁を求めよ 解法 そのまま計算するだけです。 (defun syou (n r) (/ (- n (mod n r)) r)) (defun calc (n r) (let ((m 1)) (while (< 0 r) (if (= (mod r 2) 1) (setq m (mod (* m n) 10000000000))) (setq n (mod (* n n) 10000000000)) (setq r (syou r 2)))m)) (mod (+ (* 28433 (calc 2 7830457)) 1) 10000000000 ) *問い99 ファイル内で最大の数値となる基数と指数のペアはどこか? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2099 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 < 3^7 = 2187 であることが確かめられる. しかし, 632382518061 > 519432525806 を確認することは非常に難しい (両者ともに300万桁以上になる). 各行に1組が書かれている1000個の組を含んだ22Kのテキストファイル base_exp.txt から, 最大の数が書かれている行の番号を求めよ. 注: ファイル中の最初の二行は上の例である. 解法 対数をとれば一発です。 #include<stdio.h> #include<math.h> int main(){ double a,b,ans=0; int ansR; for(int i=0;i<1000;i++){ scanf("%lf,%lf",&a,&b); if(log(a)*b>ans){ ansR=i+1; ans=log(a)*b; } } printf("%d",ansR); }
*問い91 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2091 0<=x,y<=50の格子点で直角三角形を作るとき点の一つを原点に固定した時何通りの三角形を作れるか? 解法 直角になる地点が決まれば後はベクトルの直角の概念から条件を満たす残りの点は決まります。 それを素直に計算するだけです。 #include<stdio.h> #include<algorithm> int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } int main(){ int ans=0; for(int ax=0;ax<=50;ax++){ for(int ay=0;ay<=50;ay++){ if(ax==0&&ay==0){ ans+=50*50; }else if(ax==0||ay==0){ ans+=50; }else{ int k=gcd(ax,ay); ans+=std::min((50-ay)/(ax/k),ax/(ay/k));//左上 ans+=std::min(ay/(ax/k),(50-ax)/(ay/k)); } } } printf("%d",ans); } *問い92 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2092 各桁の2乗を足し合わせて新たな数を作ることを, 同じ数が現れるまで繰り返す. 例えば   44 → 32 → 13 → 10 → 1 → 1   85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 のような列である. どちらも1か89で無限ループに陥っている. 驚くことに, どの数から始めても最終的に1か89に到達する. では, 10,000,000より小さい数で89に到達する数はいくつあるか. 解法 1000万までの数は各桁の2乗和を取ると確実に1000以下の数となるのでここまでの数を最初にメモ化して計算すれば十分です。 逆関数で89からチェーンを逆にたどればコードは少し早くなるかもしれません。 #include<stdio.h> int facter[10]={0,1,4,9,16,25,36,49,64,81}; const up=1000; int memo[up+1]={0}; int next(int n){ int re=0; while(n!=0){ re+=facter[n%10]; n/=10; } return re; } int main(){ int ans=0,num; for(int i=2;i<=up;i++){ num=i; while(num!=89&&num!=1)num=next(num); if(num==89){ ans++; memo[i]=1; } } for(int i=1000;i<1000*10000;i++){ ans+=memo[next(i)]; } printf("%d",ans); } *問い95 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2095 ある数の真の約数とは, それ自身を除く約数すべてである. 例えば, 28 の真の約数は 1, 2, 4, 7, 14 である. これらの約数の和は 28 に等しいため, これを完全数と呼ぶ. 面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており, 二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる. さらに長い鎖はあまり知られていないだろう. 例えば, 12496 から始めると, 5 つの数の鎖をなす. 12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...) この鎖は出発点に戻っているため, 友愛鎖と呼ばれる. いずれの要素も 1,000,000 を超えない最長の友愛鎖の最小のメンバーを求めよ. 解法 この問題をグラフにするとループとループに入る木構造、もしくは100万以上になってループが途絶える木構造の2種類になります。 一番長いループを探す問題なのですが、賢い方法も思いつかなかったので全部の鎖をチェックしてます。 #include<stdio.h> const int up=1000*1000; int memo[up+1]={0}; int calc(int n){ __int64 re=1; int t=n; for(int i=2;i*i<=n;i+=(i&1)+1){ int mul=1; while(n%i==0){ mul*=i; n/=i; } if(mul!=1){ re*=(mul*i-1)/(i-1); } } if(n!=1)re*=(n+1); return re-t; } int saiki(int s,int n){ if(n>=up){ return -up; } if(s==n)return 1; if(memo[n]==1)return -up; memo[n]=1; int t=saiki(s,calc(n))+1; memo[n]=0; return t; } int main(){ int ansLen=0,ans; for(int i=1;i<up;i++){ int len=saiki(i,calc(i)); if(len>ansLen){ ansLen=len; ans=i; } } printf("%d %d",ans,ansLen); } *問い97 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2097 非メルセンヌ素数 28433×2^7830457+1 の末尾10桁を求めよ 解法 そのまま計算するだけです。 (defun syou (n r) (/ (- n (mod n r)) r)) (defun calc (n r) (let ((m 1)) (while (< 0 r) (if (= (mod r 2) 1) (setq m (mod (* m n) 10000000000))) (setq n (mod (* n n) 10000000000)) (setq r (syou r 2)))m)) (mod (+ (* 28433 (calc 2 7830457)) 1) 10000000000 ) *問い99 ファイル内で最大の数値となる基数と指数のペアはどこか? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2099 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 < 3^7 = 2187 であることが確かめられる. しかし, 632382^518061 > 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる). 各行に1組が書かれている1000個の組を含んだ22Kのテキストファイル base_exp.txt から, 最大の数が書かれている行の番号を求めよ. 注: ファイル中の最初の二行は上の例である. 解法 対数をとれば一発です。 #include<stdio.h> #include<math.h> int main(){ double a,b,ans=0; int ansR; for(int i=0;i<1000;i++){ scanf("%lf,%lf",&a,&b); if(log(a)*b>ans){ ansR=i+1; ans=log(a)*b; } } printf("%d",ansR); }

表示オプション

横に並べて表示:
変化行の前後のみ表示: