問い２
フィナボッチ数のうち４００万以下の偶数の和を求める問題。
もしかしたら大きな数になるかと思ったら意外と小さい数になった。
フィナボッチ数の性質を考えたら当たり前か。
偶数項だけ見て小さい順にＡiとラベルを張っていくとAi=4*(Ai-1)+Ai-2という性質があることを利用して計算量を下げる。
出題側としてはこの数式の性質を考えてほしいのだろうと思うが、私はプログラムが書けただけで満足してしまってる。
#include<stdio.h>
int main(){
__int64 sum=2,add=0,now=2,t;
while(1){
t=now*4+add;
if(t>=4000000)break;
sum+=t;
add=now;
now=t;
}
printf("%lld\n",sum);
}
問い３
競技プログラムではないし計算量も小さいので適当な計算と出力で解く。
きっと問題Ｎｏがあがったらこんな簡単にはいかないんだろうな。
#include<stdio.h>
int main(){
__int64 a=600851475143,b=775147;
while(b>1){
while(a%b!=0&&b!=1)b--;
printf("%lld\n",b);
a=b;
b--;
}
}
問い4
３桁の数を２つ掛け算した結果回文数になってる数のうち最大の数を求める問題。
私の頭の悪さを証明するようなコードでアセプト。
#include<stdio.h>
#include<algorithm>
#include<vector>
bool isRe(int num){
if(num<=100000){
return false;
}
char cs[7];
for(int i=0;i<6;i++){
cs[i]=num%10;
num/=10;
}
bool ok=true;
for(int i=0;i<3;i++)ok=ok&&(cs[i]==cs[5-i]);
return ok;
}
int main(){
int t;
std::vector<int> res;
for(int i=100;i<1000;i++){
for(int j=100;j<1000;j++){
t=i*j;
if(isRe(t))res.push_back(t);
}
}
std::sort(res.begin(),res.end());
for(int i=0;i<res.size();i++){
printf("%d ",res[i]);
}
}
問い5
1～20まで全ての数で割りきれる最小の数を求めよという問題。
コードで解こうとしたらなんだか上手くいかなかったので大雑把にコードで求めてたらない分を手計算で補足して解いた。
サイトの目的からいって邪道な気もするので慣れたらそのうち書きなおそうと思う。
よく考えたら俺今までの人生で整数論の授業受けたことないからこれでいいかな。
何故だかわからないが３が１個取りこぼされる。
手計算で微修正して求めた答え 232792560
#include<stdio.h>
#include<math>
#include<algorithm>
int main(){
int nums[21]={0},n;
for(int i=2;i<21;i++){
n=i;
for(int j=2;j<=sqrt(i);j++){
int count=0;
while(n%j==0){
count++;
n=n/j;
}
if(nums[j]<count){
nums[j]=count;
}
}
if(n==i)nums[i]++;
}
__int64 ans=1;
for(int i=2;i<21;i++){
if(nums[i]>0){
printf("(%d %d,%d>",i,nums[i]);
ans*=i*nums[i];
}
}
printf(" %lld",ans);
}
問い6
昔一人で勉強していた数学の教科書の内容を思い出して解く。
int64は便利だなと思う。
Ｃにコボル並みの１０進型が標準であればもっと便利なんだけど。
#include<stdio.h>
int main(){
__int64 t=100,sum1,sum2=(t*(t+1))/2;
sum1=((((__int64)t)*(t+1))*(2*t+1))/6;
printf("%lld",sum2*sum2-sum1);
}
問い7
10001番目の素数を求める問題。
篩で一発。
計算量を気にしなくていいって楽でいいなあ。
#include<stdio.h>
#include<math.h>
#include<string.h>
int main(){
const int up=1000000;
bool so[up];
memset(so,true,sizeof(so));
for(int i=2;i<=sqrt(up);i++){
if(so[i]==false)continue;
for(int j=i*2;j<up;j+=i){
so[j]=false;
}
}
int count=0,i;
for(i=2;i<up;i++){
count+=so[i];
if(count==10001)break;
}
printf("%d\n",i);
}
問い8
１０００桁の数字の中の連続した５つの数字を取り出し各桁の積を求める。
最大値を求めよという問題。
数値が小さいので気楽に解ける。
#include<stdio.h>
int main(){
char s[1002]="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
int sum,ans=0;
for(int i=0;i<1000-4;i++){
sum=1;
for(int k=0;k<5;k++){
sum*=(s[i+k]-'0');
}
if(ans<sum)ans=sum;
}
printf("%d\n",ans);
}
問９
a+b+c=1000 a<b<c a^2+b^2=c^2を満たすa,b,cの積を求めよ。
計算量が小さいので全探索。
これ後半の問題で大きな数字になってリベンジしてきそうな予感のする問題。
#include<stdio.h>
int main(){
int ans;
for(int a=1;a<999;a++){
for(int b=a+1;b<1000-a&&b>a;b++){
int c=1000-a-b;
if(c<=b)break;
if(a*a+b*b==c*c){
printf("%d %d %d ",a,b,c);
ans=a*b*c;
}
}
}
printf("%d\n",ans);
}
問い10
解き終わった問題で他の人の答えを見てると整数論の知識を使った賢い答えが見つかる。
うーん自分の素朴な解法が恥ずかしいが整数論の基礎教育受けたことないから何ともならないんだ、、、
素朴な解法で進めるところまで進もう。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
const int up=2000000;
bool so[up];
int main(){
memset(so,true,sizeof(so));
for(int i=3;i<=sqrt(up);i+=2){
if(so[i]==false)continue;
for(int j=i*3;j<=up;j+=i*2){
so[j]=false;
}
}
__int64 sum=2;
for(int i=3;i<=up;i+=2){
sum+=so[i]?i:0;
}
std::cout<<sum;
}
最終更新：2012年08月25日 10:47
