問い91
解法
直角になる地点が決まれば後はベクトルの直角の概念から条件を満たす残りの点は決まります。
それを素直に計算するだけです。
#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
解法
そのまま計算するだけです。
(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 ファイル内で最大の数値となる基数と指数のペアはどこか?
解法
対数をとれば一発です。
#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);
}
最終更新:2013年01月04日 04:52