「オイラープロジェクト41～50」の編集履歴（バックアップ）一覧に戻る
オイラープロジェクト41～50 - (2012/09/01 (土) 05:06:17) のソース
*問い41
n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつもつこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ.
パンデジタル数を大きい順に順列で生成して後は素数かどうか簡易検査するだけです。
#include<stdio.h>
#include<math.h>
bool perms[10];
int ans=-1;
bool isSosuu(int n){
//素数かどうかの簡易チェック
int m=sqrt(n);
if(n==m*m||n%2==0)return false;//２の倍数かｍで割り切れるなら
for(int i=3;i<m;i+=2){
if(n%i==0)return false;//奇数で割ってみる
}
return true;
}
void saiki(int sum,int deep,int k){
if(deep==k){
//printf("%d\n",sum);
if(isSosuu(sum)==true){
ans=sum;
}
}else{
for(int i=k;i>0;i--){
if(perms[i]==true){
perms[i]=false;
saiki(sum*10+i,deep+1,k);
if(ans!=-1)return ;
perms[i]=true;
}
}
}
}
int main(){
perms[0]=false;
for(int i=9;i>0;i--){
//桁数i
for(int j=1;j<=i;j++)perms[j]=true;
saiki(0,0,i);
if(ans!=-1)break;
}
printf("%d\n",ans);
}
*問い42
三角語と呼ばれる単語がテキストファイルの中にいくつあるか数える問題。
最大値の見極めがつかないので少しメモリをぜいたくに使って後は愚直に一つずつ計算。
まあ計算すればいいわけだけどファイルは中身が見えないブラックなファイルとして扱いたいし、練習問題でコードサイズは膨らましたくないのでこのコードに落ち着いた感じ。
#include <stdio.h>
#include <string.h>
#include <map>
int main(){
FILE *fp;
if((fp=fopen("words.txt","r"))==NULL){
printf("fileOpenError");
exit(EXIT_FAILURE);
}
char text[102];
int max=0;
std::map<int,int> memo;
while(fscanf(fp,"\"%[^\"]\",",text)>0){
int sum=0;
for(int i=0;i<strlen(text);i++){
sum+=text[i]-'A'+1;
}
//printf("(%s %d %d)",text,sum,max);
if(max<sum)max=sum;
if(memo.find(sum)!=memo.end()){
memo[sum]++;
}else{
memo[sum]=1;
}
}
fclose(fp);
int t=0,ans=0;
for(int i=1;t<=max;i++){
t=((i+1)*i)/2;
ans+=memo.find(t)!=memo.end()?memo[t]:0;
}
printf("%d\n",ans);
}
*問い43
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分語が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406は2で割り切れる
d3d4d5=063は3で割り切れる
d4d5d6=635は5で割り切れる
d5d6d7=357は7で割り切れる
d6d7d8=572は11で割り切れる
d7d8d9=728は13で割り切れる
d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.
saiki関数をつかってパンデジタル数を順列生成しチェック関数で条件を満たすかチェックします。
#include<stdio.h>
#include<math.h>
#include<iostream>
bool perms[10];
__int64 ans=0;
bool check(__int64 n){
int so[]={17,13,11,7,5,3,2};
for(int i=0;i<7;i++){
if((n%1000)%so[i]!=0){
return false;
}
n/=10;
}
return true;
}
void saiki(__int64 sum,int deep){
if(deep==10){
if(check(sum)==true){
std::cout<<sum<<" ";
ans+=sum;
}
}else{
for(int i=0;i<10;i++){
if(deep==0&&i==0)continue;//先頭は0になってはいけない
if(perms[i]==true){
perms[i]=false;
saiki(sum*10+i,deep+1);
perms[i]=true;
}
}
}
}
int main(){
for(int i=0;i<10;i++)perms[i]=true;
saiki(0,0);
std::cout<<"\n\n"<<ans;
}
*問い44
5角数Pi,Pjについて考える。
Pi+PjとD=|Pi-Pj|の両方が5角数になる時の最小のＤを答えよ。
とりあえず最初に見つかった条件を満たす数を投稿したら合格したものの、厳密にはきちんとは解けてない問題。
このコードはもっと大きな数の差分に条件を満たす数がないか続きを調べさせるといつまでも計算が終わらない。
#include<stdio.h>
#include<set>
#include<iostream>
int main(){
__int64 min=-1,num1,num2,i=2,j,ansD,ansUP;
std::set<__int64> memo,next;
std::set<__int64>::reverse_iterator it;
memo.insert(1);
while(1){
num1=(i*(3*i-1))/2;
j=i-1;
num2=(j*(3*j-1))/2;
if(min>-1&&num1-num2>=min)break;
__int64 k=i+1;
next.clear();
while((k*(3*k-1))/2<=num1*2){
next.insert((k*(3*k-1))/2);
k++;
}
for(it=memo.rbegin();it!=memo.rend();it++){
if((*it)>num1)continue;
num2=num1-(*it);
if(min>-1&&num2>=min)break;
if((min==-1||min>num2)&&memo.find(num2)!=memo.end()&&next.find(num1+(*it))!=next.end()){
min=num2;
ansUP=num1;
ansD=(*it);
std::cout<<min<<" "<<ansUP<<" "<<ansD;
return 0;
}
}
memo.insert(num1);
i++;
}
}
*問い45
三角数∧５角数∧6角数∧40755より大きな最小の数を求めよ。
マージソートの考え方で小さい分を少しずつ増量させればいいです。
意外と大きな数が答えになりました。
#include<stdio.h>
#include<iostream>
int main(){
__int64 n3=286,n5=166,n6=144,p3,p5,p6;
p3=(n3*(n3+1))/2;
p5=(n5*(3*n5-1))/2;
p6=(n6*(2*n6-1));
while(p3!=p5 || p5!=p6 || p3!=p6){
if(p3<=p5 && p3<=p6){
n3++;
}else if(p5<=p3 && p5<=p6){
n5++;
}else if(p6<=p3 && p6<=p5){
n6++;
}
p3=(n3*(n3+1))/2;
p5=(n5*(3*n5-1))/2;
p6=(n6*(2*n6-1));
//std::cout<<p3<<" "<<p5<<" "<<p6<<"\n";
}
std::cout<<p3<<" "<<p5<<" "<<p6;
}
*問い46
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.
答えは5777、あのゴールドバッハがこんな小さな数で間違いが出る予想をするというのも面白い。
おそらく理論的に考えて理論的ミスを犯したんだろうな。
#include<stdio.h>
#include<vector>
#include<algorithm>
const int up=1000000;
std::vector<int> kiGousei;
bool so[up];
void setKiGousei(){
int i2;
memset(so,true,sizeof(so));
for(int i=0;i<=up;i+=2)so[i]=false;//まあ大した計算量じゃないし手抜き
so[1]=false;
so[2]=true;
for(int i=3;i<=up;i+=2){
if(so[i]==false){
kiGousei.push_back(i);
}else{
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
}
int main(){
setKiGousei();
//for(int i=0;i<10;i++){
//printf("%d ",kiGousei[i]);
//}
int n,m;
for(int i=0;i<kiGousei.size();i++){
n=kiGousei[i];
bool hit=false;
for(int j=1;2*j*j<n;j++){
m=n-2*j*j;
if(so[m]==true){
hit=true;
break;
}
}
if(hit==false){
printf("%d",n);
break;
}
}
}
*問い47
連続する2つの数がそれぞれ2つの異なる素因数を持つのは
14 = 2 × 7
15 = 3 × 5 の場合である.
同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは
644 = 22 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19 の場合である.
連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.
2^2*3^2と2^1*3^2は全て同じ素因数を持つので異なる場合とは考えないようです。
少し問題が分かりにくいですね。
#include<stdio.h>
#include<string.h>
const int up=1000000;
bool so[up];
void setSo(){
int i2;
memset(so,true,sizeof(so));
for(int i=0;i<=up;i+=2)so[i]=false;
so[2]=true;
so[1]=false;
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
int check(int n){
int p,m;
int size=0,re=1;
if(so[n]==true)return -1;//素数なら１つしか素因数を持たない
for(int p=2;p*p<=n;p++){
if(n%p!=0)continue;//nをpで割りきれなかったら
size++;
m=n/p;
if(so[m]==true&&m!=p){
size++;
re*=m;
while(n%m==0)n/=m;
}
if(size>4)break;//４つ以上割れてしまった
while(n%p==0){
n/=p;
}
re*=p;
}
//printf("(%d %d)",size,n);
//printf("\n");
return (size==4&&n==1)?re:-1;//４つの素因数で割り切れて1になっていた
}
int main(){
setSo();
int a[4];
for(int i=0;i<=up;i++){
//まあ試しに１００万以下で探す
bool ok=true;
for(int j=0;j<4;j++){
a[j]=check(i+j);
//printf("%d ",a[j]);
if(a[j]==-1){
ok=false;
}
for(int k=0;k<j;k++){
if(a[k]==a[j]){
ok=false;
}
}
//if(ok==false)break;
}
if(ok==true){
printf("\nans=%d",i);
break;
}
}
}
*問い48
Σi^i(i=1...1000)の下１０ケタを求めよという問題。
int main(){
__int64 ans=0,b,m=10000000000;
for(int i=1;i<1001;i++){
b=1;
for(int j=0;j<i;j++){
b=(b*i)%m;//ここは工夫して計算量を落としてもいいんだけどたった１００万回だしまあいいか
}
ans=(ans+b)%m;
}
std::cout<<ans;
}
*問い49
項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。
(i)3つの項はそれぞれ素数である。
(ii)各項は他の項の置換で表される。
1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが、4桁の増加列にはもう1つ存在する。
それではこの数列の3つの項を連結した12桁の数を求めよ。
素数P1と素数P2の差分を取ってp1+2*(p2-p1)とすれば等差数列の３項目が求まるのでp3が素数かチェックしてから、p1,p2とp2,p3の各桁に出てくる数字の対応を数えればチェックが出来ます。
#include<stdio.h>
#include<string.h>
#include<vector>
const int up=10000;
bool so[up];
std::vector<int> sosuu;
void setSo(){
int i2;
memset(so,true,sizeof(so));
for(int i=0;i<=up;i+=2)so[i]=false;
so[2]=true;
so[1]=false;
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
if(i>1000)sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<up;j+=i2){
so[j]=false;
}
}
}
bool check(int p1,int p2){
int count[10]={0};
while(p1!=0){
count[p1%10]++;
p1/=10;
}
while(p2!=0){
count[p2%10]--;
p2/=10;
}
bool ok=true;
for(int i=0;i<10;i++)ok=(ok&&(count[i]==0));
return ok;
}
int main(){
setSo();
int p1,p2,p3;
for(int i=0;i<sosuu.size();i++){
p1=sosuu[i];
for(int j=i+1;j<sosuu.size();j++){
p2=sosuu[j];
p3=2*(p2-p1)+p1;
if(p3>=10000)break;
if(so[p3]==false)continue;
if(check(p1,p2)&&check(p2,p3)){
printf("(%d %d %d)",p1,p2,p3);
}
}
}
}
