※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

大学への数学 マスターオブ整数論の問題をプログラムで解いてみた。

問い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);
}