「周期性と対称性」の編集履歴（バックアップ）一覧に戻る

周期性と対称性 - (2012/11/28 (水) 12:30:22) のソース

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

問い３-1-1
５００までの数の3の倍数と4の倍数を○で囲んだとき○の数は何個になるか？

問い３-１-２
５００までの数の3の倍数と4の倍数を○で囲んだとき１差になる○は何個あるか？


 #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("問い１答え %d",ans0);
	return ans;
 }
 int main(){
	
	printf("\n問い２答え %d",calc(3,4,500));
 }





問い4-２
自然数から２の倍数、３の倍数、５の倍数を取り除いたとき５０番目の数を求めよ。
またその数の和を求めよ。

 #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
問い１　123^99の１の位を求めよ
問い２　1＾4-１～100＾4-1が１０の倍数になる数はいくつあるか？


 #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
１０００個目までのファイナボッチ数列に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);
 }