「オイラープロジェクト21～30」の編集履歴（バックアップ）一覧に戻る
オイラープロジェクト21～30 - (2012/10/09 (火) 09:53:23) のソース
*問い21
自然数nの約数の合計から自分自身を除いた約数の和d(n)を定義する。
10000以下のd(d(n))=n∧n!=d(n)となる自然数の合計を求めよ。
#include<stdio.h>
int d(int n){
int sum=0;
for(int i=1;i<n;i++){
if(n%i==0)sum+=i;
}
return sum;
}
int main(){
int ans=0,t;
for(int i=2;i<10000;i++){
t=d(i);
if(t<10000 && i==d(t) && i!=t){
ans+=i;
}
}
printf("\nans=%d",ans);
}
*問い22
名前のリストを並べ替えてスコアを算出せよという問題。
うーんファイル入出力の初歩の問題かな？
#include<vector>
#include <stdio.h>
#include <string>
#include<algorithm>
#include<iostream>
int main(){
FILE *fp;
std::vector<std::string> names;
if((fp=fopen("names.txt","r"))==NULL){
printf("fileOpenError");
exit(EXIT_FAILURE);
}
char text[102];
while(fscanf(fp,"\"%[^\"]\",",text)>0){
names.push_back(text);
}
std::sort(names.begin(),names.end());
__int64 ans=0,m;
for(int i=0;i<names.size();i++){
//printf("%s ",names[i].c_str());
std::string str=names[i];
m=0;
for(int j=0;j<str.size();j++){
m+=str[j]-'A'+1;
}
if(i==937){
//確認用
std::cout<<str<<" "<<i+1<<" "<<m<<" ";
}
ans+=(i+1)*m;
}
fclose(fp);
std::cout<<ans;
}
*問い２３
小さい数からメモ化して解いた。
素因数分解の一意性を使って解く。
例えば2^3*3^2=72の約数は1 2 3 4 6 8 9 12 18 36
これを例えば３倍すると72*3=216
約数全体は
A 1 2 3 4 6 8 9 12 18 36
を３倍した
B 3 6 9 12 24 27 36 54 108
AとＢの和集合となる。
これが5倍をＣとした場合
ＡとＣの共通集合は無くなります。
72を5倍した数の約数は
Ａ+Ｃとなります。
3倍だと216の約数の和-72の約数の和-1=Ｂ-Ａとなります。
この性質を使えばある数bとその約数が分かってるとき適当な自然数aを書けるとabの約数の和が簡単に算出できます。
これを使ってそこそこ高速なコード実行速度で解いてみました。
#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=28124;
std::vector<int> sosuu,ups;
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 ans[up]={0};
void saiki(__int64 num,__int64 u,int d,__int64 m,__int64 base){
if(num>=up)return ;
ans[(int)num]=u-num;
if(u-num>num){
ups.push_back(num);//超過数のリスト
}
int temp;
for(int i=d;i<sosuu.size();i++){
//小さい数から
if(num*sosuu[i]>=up)break;
if(i==d){
saiki(num*sosuu[i],base*m*sosuu[i]+u,i,m*sosuu[i],base);//同じ数が連続でかけられた場合増えた差分だけ足しこむ
}else{
saiki(num*sosuu[i],u*(sosuu[i]+1),i,sosuu[i],u);
//手前二つの引数が数値の増加と、約数の和の増加、iがsosuuを小さい数から掛けていくためのポインタ、
//4つめと５つ目の引数は連続して同じ数が掛けられた時のための差分計算用引数
}
}
}
int main(){
setSo();
ans[1]=0;
saiki(1,1,0,1,1);
bool oks[up];
memset(oks,true,sizeof(oks));
//ここバイナリサーチかstd::mapにすればもう少し早くなる。
for(int i=0;i<ups.size();i++){
for(int j=i;j<ups.size();j++){
int t=ups[i]+ups[j];
if(t<up)oks[t]=false;
}
}
int ans=0;
for(int i=1;i<up;i++){
ans+=oks[i]*i;
}
printf("%d",ans);
}
*問い24
0～9までの数字を一つずつ並べてできる文字列のうち１００万番目にくる数字を答える問題。
普通に全探索してもよいのだけど。
枝が均質な構造をしているということを利用して計算して解きます。
計算量はO(100)位？
#include<stdio.h>
int main(){
int perms[10];
int k=1;
for(int i=0;i<10;i++){
perms[i]=k;
k*=(i+1);
//printf("%d ",perms[i]);
}
//printf("\n");
int no;
scanf("%d",&no);
no--;
int ans[10];
int memo[10]={0};
for(int i=9;i>=0;i--){
ans[i]=no/perms[i];
no%=perms[i];
int temp=0;
for(int j=0;j<10;j++){
if(temp==ans[i]&&memo[j]==0){
ans[i]=j;
memo[j]=1;
break;
}
if(memo[j]==0){
temp++;
}
}
printf("%d",ans[i]);
}
}
*問い25
フィナボッチ数列が１０００ケタを超えるのは数列の何個目か答える問題。
人生で２回目に自分で考えて書いたＬｉｓｐコードなので最初Ｌｏｏｐのなかに余分な（を入れてsetqのあたりが余分な関数として解釈されてしまっていた。
掲示板で修正してもらってアセプト。
（人からアドバイスをもらったので一応カンニングして解いた問題に分類）
(defun getUP (n)
(if (= n 0)
1
(* 10 (getUP (1- n)))))
getUP
(defun calc ()
(let *1 )
(loop
(setq n3 (+ n1 n2))
(if (>= n3 up) (return i))
(setq n1 n2)
(setq n2 n3)
(incf i 1))))
calc
(calc)
*問い26
自然数ｄ<１０００の時1/dの循環小数が最も長くなる数を答えよという問題。
大昔、本の半分を費やして循環小数の高速で低メモリな判別法について書かれた本を読んだ覚えはある。
しかし大昔のことなので全く思い出せず素朴な割り算とメモ化で判別。
#include<stdio.h>
#include<set>
struct A{
int syo,amari,no;
bool operator<(const A& a)const{
if(syo!=a.syo)return syo<a.syo;
return amari<a.amari;
}
};
std::set<A> memo;
int ans,mymax;
void saiki(int num,int d,int deep){
A a;
a.syo=num/d;
a.amari=num%d;
//printf("(%d %d %d)",num/d,num%d,deep);
if(memo.find(a)==memo.end()){
a.no=deep;
memo.insert(a);
saiki(num%d*10,d,deep+1);
}else{
//printf("<%d %d>",deep,(memo.find(a))->no);
int t=deep-(memo.find(a))->no;
if(t>mymax){
mymax=t;
ans=d;
}
}
}
int main(){
mymax=0;
for(int i=1;i<1000;i++){
memo.clear();
saiki(1,i,0);
}
printf("%d %d\n",ans,mymax);
}
*問い27
オイラーは以下の二次式を考案している:
n2 + n + 41.
この式は, nを0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40のとき402 + 40 + 41 = 40(40 + 1) + 41となり41で割り切れる. また, n = 41のときは412 + 41 + 41であり明らかに41で割り切れる.
計算機を用いて, 二次式 n2 - 79n + 1601という式が発見できた. これはn = 0 から 79 の連続する整数で素数を生成する. 係数の積は, -79 × 1601 で -126479である.
さて, |a| < 1000, |b| < 1000 として以下の二次式を考える (ここで|a|は絶対値):
n2 + an + b
n=0から始めて連続する整数で素数を生成したときに最長の長さとなる上の二次式の, 係数a, bの積を答えよ.
解法
ｎ＝0の時ｂは素数でないといけないのでそこだけ注意して後は全探索します。
この問題、他の正答者のコードを見るに漸化式らしきものを使った非常に賢い高速な解法と全探索の解法と二つに分かれるようです。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
const int up=1000000;
std::vector<int> sosuu;
bool so[up+1];
void setSo(){
int i2;
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
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();
int a,b,c,ans=0,ansA,ansB,n;
for(int i=0;sosuu[i]<1000;i++){
b=sosuu[i];
for(a=-b+1;a<1000;a++){
n=0;
while(1){
c=n*n+a*n+b;
if(c<1||so[c]==false)break;
n++;
}
if(ans<n){
ans=n;
ansA=a;
ansB=b;
}
}
}
std::cout<<ansA<<" "<<ansB<<" "<<ansA*ansB<<" "<<ans;
}
*問い28
http://projecteuler.net/problem=28
中心かららせん状に数字が増加するとき対角線の合計は幾つとなるか？
規則的に増加するだけなのでそれを足し合わせるだけです。
#include<stdio.h>
int main(){
__int64 sum=1,add,num=1;
for(int i=0;i<500;i++){
add=(i+1)*2;
for(int j=0;j<4;j++){
num+=add;
//printf("%d ",num);
sum+=num;
}
}
printf("(%d)",sum);
}
*問い29
Ｌｉｓｐなら力づくで100乗とか求めても大丈夫なのだろうけどＣ++で少しスマートに計算することに。
まあ底辺ホビープログラマのおいらのやるスマートなんてこの程度っと♪
aを素因数分解の一意性で分解して素数何個掛けられてるかｂを掛けて判別。
#include<stdio.h>
#include<set>
struct S{
int so[25];
bool operator<(const S& s)const{
for(int i=0;i<25;i++){
if(so[i]!=s.so[i])return so[i]<s.so[i];
}
return false;
}
};
int ans=0;
std::set<S> memo;
int so[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
void dataSet(int a,int b){
S s;
memset(s.so,0,sizeof(s.so));
for(int i=0;i<25;i++){
while(a%so[i]==0){
a/=so[i];
s.so[i]++;
}
s.so[i]*=b;
}
if(memo.find(s)==memo.end()){
ans++;
memo.insert(s);
}
}
int main(){
for(int a=2;a<101;a++){
for(int b=2;b<101;b++){
dataSet(a,b);
}
}
printf("%d",ans);
}
*問い30
数字の各桁を5乗して足し合わせたものが元の数字と同じになる場合がある。
この条件を見たす全ての数を足し合わせると幾らになるか？
各桁は9＾5乗<100000なので一ケタ増えても100000以上増えない。
よって1000000以下までのすべての数字をチェックすれば良い。
#include<stdio.h>
int main(){
int n,a,sum,ans=0;
for(int i=2;i<1000000;i++){
n=i;
sum=0;
for(int j=0;j<6;j++){
a=n%10;
sum+=a*a*a*a*a;
n/=10;
}
if(i==sum){
printf("%d ",i);
ans+=i;
}
}
printf("\n\n%d",ans);
}
