「プロジェクトオイラー問い21～30」の編集履歴（バックアップ）一覧に戻る
*問い21
d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.
例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.
それでは10000未満の友愛数の和を求めよ.
解法
コードの中では1～ｎまでの約数を求める計算はsetYakusuu関数で簡単に方がついてます。
後は条件を満たすかどうかmain関数のなかで調べるだけです。
#include<stdio.h>
const int up=10000;
int memo[up+1]={0};
void setYakusuu(){
for(int i=1;i<=up;i++){
for(int j=2*i;j<=up;j+=i){
memo[j]+=i;
}
}
}
int main(){
setYakusuu();
int d,ans=0;
for(int i=2;i<up;i++){
d=memo[i];
if(d<up&&memo[d]==i&&d!=i){
printf("%d %d\n",d,i);
ans+=i;
}
}
printf("%d",ans);
}
*問い22
5000個以上の名前が書かれている46Kのテキストファイル names.txt を用いる. まずアルファベット順にソートせよ.
のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.
たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは 3 + 15 + 12 + 9 + 14 = 53 という値を持つ. よってCOLINは 938 × 53 = 49714 というスコアを持つ.
ファイル中の全名前のスコアの合計を求めよ.
解法
この問題回答者が二つのグループに分かれる気がします。
テキスト処理が得意なスクリプト言語の性能を最大限に引き出し数行のコードで問題を解く人と普通に３０行程度使って解く人です。
私はC++で解いてるので後者です。
C++でもコードを工夫すれば短くなるかな？
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<string>
#include<algorithm>
int main(){
FILE *fp;
char name[256],c;
std::string strName;
if((fp=fopen("euler22Data.txt","r"))==NULL){
printf("file open Error");
exit(EXIT_FAILURE);
}
std::vector<std::string> names;
while(1){
fscanf(fp,"\"%[^\"]\"",name);
names.push_back(name);
if(fscanf(fp,"%c",&c)==EOF)break;
}
std::sort(names.begin(),names.end());
int ans=0;
for(int i=0;i<names.size();i++){
strName=names[i];
int sum=0;
for(int j=0;j<strName.size();j++){
sum+=strName[j]-'A'+1;
}
ans+=sum*(i+1);
}
fclose(fp);
printf("%d",ans);
}
*問い23
ある数ｍはｍの倍数になる数は全てｍを約数に持ちます、つまりｍの倍数の約数の和にはすべてｍを足しておくといいわけです。
これを利用してsetKazyousuu関数のなかで約数の和をmemoに入れていきます。
計算を高速化するために過剰数になった数だけmemo[i]=-1と入れておきます。
後はmainループの中で過剰数を調べればコード実行時間０．０１６秒となります。
#include<stdio.h>
#include<stdio.h>
#include<vector>
#include<time.h>
const int up=28123;
int memo[up+1]={0};
std::vector<int> kazyou;
void setKazyousuu(){
for(int i=1;i<=up;i++){
if(i<memo[i]){
kazyou.push_back(i);
memo[i]=-1;
}
for(int j=2*i;j<=up;j+=i){
memo[j]+=i;
}
}
}
int main(){
double start=clock();
setKazyousuu();
int k,ans=0;
for(int i=1;i<up;i++){
bool ok=true;
for(int j=0;j<kazyou.size()&&2*kazyou[j]<=i;j++){
if(memo[i-kazyou[j]]==-1){
ok=false;
break;
}
}
if(ok==true){
//printf("%d ",i);
ans+=i;
}
}
printf("\nans=%d %lf",ans,clock()-start);
}
*問い24
順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると
012 021 102 120 201 210
になる.
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?
解法
先頭桁が0になる数字列は３６２８８０通り、1も２も３６２８８０通りです。
なので組み合わせ数で割っていけば最初の数は２であると分かります。
２桁目以降は40320通りのどれかに分岐します。
この時一度使った数は使えないということに注意して求めていきます。
それだけの簡単な問題です。
#include<stdio.h>
int base[11]={0,362880,40320,5040,720,120,24,6,2,1,1};
int main(){
int no=1000*1000-1;
bool spents[10];
for(int i=0;i<10;i++)spents[i]=false;
for(int i=1;i<11;i++){
int p=no/base[i]+1;
int count=0,j;
for(j=0;j<10;j++){
count+=!spents[j];
if(count>=p)break;
}
//2783915460
spents[j]=true;
printf("%d",j);
no=no%base[i];
}
}
*問い25
フィボナッチ数列で１０００ケタになる最初の項を求めよ。
解法
Lispで解いてもよいですし精度の高い近似式で解いてもよかったのですが簡単な近似式があったのでそちらを使いました。
１０００桁近辺はこの近似式が精度を保てるギリギリの値みたいです。
#include<stdio.h>
#include<math.h>
int main(){
double b=(999+0.349)/0.209;
printf("%d",(int)(b+0.5));
}
*問い26
d < 1000 なる 1/d の中で循環節が最も長くなるような d を求めよ。
解法
Wikiの循環節に関する記事を参考にコードを書いてみました。
#include<stdio.h>
#include<algorithm>
const int up=1000;
int calc(){
int ansSize=0,ans=0;
for(int i=2;i<up;i++){
int ten=10,count=1;
if(i%2==0||i%5==0){
count=0;//2か5で割れる数は循環しない
}else{
while(ten%i!=1){
ten=(ten*10)%i;//循環節の長さを求める
count++;
}
}
if(ansSize<count){
ansSize=count;//循環節の最大長が更新された
ans=i;//答えの数字
}
}
return ans;
}
int main(){
printf("%d",calc());//答えの表示
}
*問い27
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2027
x^2+ax+bでｘ>=0の連続した自然数とした時最も長く素数を生成するa,bの積を答えよ。
ただし|a|,|b|ともに1000以下とする。
解法
全部検証するコードしか思いつかない。
#include<stdio.h>
#include<algorithm>
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
int ansA,ansB,ansLen=0;
for(int a=-999;a<1000;a++){
for(int b=std::max(-1+a+2,-999);b<1000;b++){
int x;
for(x=0;isPrime(x*x+a*x+b);x++);
if(x>ansLen){
ansLen=x;
ansA=a;
ansB=b;
}
}
}
printf("%d",ansA*ansB);
}
*問い28
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2028
らせん状に数字が増加していく表で対角線の合計を求めよという問題。
解法
計算量が小さいのでシンプルにそのまま実装してみました。
規則的なので数式一つにまとまりそうです。
#include<stdio.h>
int main(){
int ans=1,add=1;
for(int i=1;i<=500;i++){
for(int j=0;j<4;j++){
add+=2*i;
ans+=add;
}
}
printf("%d",ans);
}
*問い29
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2029
a^b,2<=a<=100 2<=b<=100。
解法
素因数分解の一意性を使って素数の累乗で数字を表現して後はstd::setに放り込むだけです。
#include<stdio.h>
#include<map>
#include<set>
std::map<int,int> calc(int a,int b){
std::map<int,int> re;
for(int i=2;i<=a;i++){
int count=0;
while(a%i==0){
a/=i;
count++;
}
if(count!=0)re[i]=count*b;
}
return re;
}
int main(){
std::set<std::map<int,int> > all;
for(int a=2;a<=100;a++){
for(int b=2;b<=100;b++){
all.insert(calc(a,b));
}
}
printf("%d",all.size());
}
*問い30
各桁の５乗を求めその和をとるとき、元の数と同じになる数の和はいくつか？
解法
桁が増えても数の和は9^5以上のペースで増えないので上限が35万近辺にあると分かります。
少し余裕を見て４０万でアセプトしました。
こんな問題でも賢いコードってあるものだろうか？
#include<stdio.h>
int main(){
int n,ans=0;
for(int i=2;i<40*10000;i++){
int mod=1,num=i,sum=0;
for(int j=0;j<6;j++){
n=(num/mod)%10;
mod*=10;
sum+=n*n*n*n*n;
}
if(sum==i){
printf("%d ",i);
ans+=i;
}
}
printf("%d",ans);
}
