大学への数学 マスターオブ整数論の問題をプログラムで解いてみた。
問い3-1-1
500までの数の3の倍数と4の倍数を○で囲んだとき○の数は何個になるか?
問い3-1-2
500までの数の3の倍数と4の倍数を○で囲んだとき1差になる○は何個あるか?
#include<stdio.h>
#include<set>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
int calc(int a,int b,int limit){
int u=a*(b/gcd(a,b));
int ans=0,ans0;
std::set<int> memo;
std::set<int>::iterator it1,it2;
int up=(limit>=u)?u:limit;
for(int i=a;i<=up;i+=a)memo.insert(i);
for(int i=b;i<=up;i+=b)memo.insert(i);
if(memo.size()==0)return 0;
it1=memo.begin();
it2=memo.begin();
for(it2++;it2!=memo.end();it1++,it2++){
if((*it2)-(*it1)==1)ans++;
}
if(u>=limit)return ans;
ans=ans*(limit/u);
ans0=memo.size()*(limit/u);
up=limit%u;
it1=memo.begin();
it2=memo.begin();
int count=0;
for(it2++;it2!=memo.end()&&(*it2)<=up;it1++,it2++){
if((*it2)-(*it1)==1)ans++;
ans0++;
count++;
}
ans0+=(count!=0);
printf("問い1答え %d",ans0);
return ans;
}
int main(){
printf("\n問い2答え %d",calc(3,4,500));
}
問い4-2
自然数から2の倍数、3の倍数、5の倍数を取り除いたとき50番目の数を求めよ。
またその数の和を求めよ。
#include<stdio.h>
void calc(int a,int b,int c,int no){
int count=0,ans=0,i;
for(i=1;count<no;i++){
if(i%a!=0 && i%b!=0 && i%c!=0){
count++;
ans+=i;
}
}
printf("%d %d",i-1,ans);
}
int main(){
calc(2,3,5,50);
}
問い4-3
問い1 123^99の1の位を求めよ
問い2 1^4-1~100^4-1が10の倍数になる数はいくつあるか?
#include<stdio.h>
int calc(int a,int b){
int memo[10]={0},count=0,c;
a%=10;
c=a;
while(memo[c]==0){
printf("(%d %d)",c,count);
memo[c]=++count;
if(count==b)return c;
c=(c*a)%10;
}
int k=(b-memo[c]+1)%(count-memo[c]+1)-1;
c=a;
for(int i=0;i<k;i++)c=(c*a)%10;
return c;
}
int calc2(int n){
int ans,count=0;
for(int i=0;i<10;i++){
int a=i%10;
if((a*a*a*a)%10==1){
count++;
}
}
ans=count*(n/10);
count=0;
for(int i=0;i<=n%10;i++){
int a=i%10;
if((a*a*a*a)%10==1){
count++;
}
}
return ans+count;
}
int main(){
printf(" %d",calc(123,99));
printf("\n%d",calc2(100));
}
問い4-4
1000個目までのファイナボッチ数列に7は何個含まれるか?
#include<stdio.h>
#include<string.h>
void calc(int n){
int memo[10][10];
memset(memo,0,sizeof(memo));
int fa=1,fb=1,t;
int count=1,count7=0;
while(memo[fa][fb]==0){
if(count>=n-1){
printf("%d ",fa);
return ;
}
memo[fa][fb]=count++;
t=fa+fb;
fb=fa%10;
fa=t%10;
if(fa==7)count7++;
}
count--;
int ans=count7*(n/count);
int k=n%count;
count=2;
fa=fb=1;
while(k>count){
t=fa+fb;
fb=fa%10;
fa=t%10;
if(fa==7)ans++;
count++;
}
printf("%d %d",count7,ans);
}
int main(){
calc(1000);
}
問い4-5
{5/7}+[10/7]+,,,+[245/7]+[250/7]の合計を求めよ。
ただし[]は整数部分を返す関数とする。
#include<stdio.h>
int calc(int a,int b,int limit){
int ans=0;
for(int i=a;i<=limit;i+=a){
ans+=(i/b);
}
printf("%d",ans);
}
int main(){
calc(5,7,250);
}
最終更新:2012年11月28日 12:30