「素因数分解の利用2」の編集履歴(バックアップ)一覧に戻る

素因数分解の利用2 - (2012/11/27 (火) 19:30:36) のソース

マスターオブ整数論 大学への数学

*問い2-1
3/xが丁度小数点以下3桁となる既約分数は何個あるか?


 #include<stdio.h>
 int yakusuuCount(int n){
	int re=1;
	for(int i=2;i*i<=n;i++){
		int count=1;
		while(n%i==0){
			n/=i;
			count++;
		}
		re*=count;
	}
	if(n!=1)re++;
	return re;
 }
 int calc1(int n,int keta){
	return (yakusuuCount(n))*((keta+1)+(keta));
 }
 int main(){
	printf("%d",calc1(3,3));
 }




*問い2-2

(384-12m)が自然数となるようなmを全て求めよ。
√(7n)<42となるnの和を全て求めよ。


 #include<stdio.h>
 #include<math.h>
 void calc(int m,int n){
	for(int i=1;i*n<m;i++){
		int k=sqrt(m-n*i);
		if(k*k==m-n*i)printf("%d ",i);
	}
 }
 int calc2(int n,int m){
	int re=0;//本当は素因数分解をりようして桁あふれが起きないように計算するのだけどまあ手抜き
	for(int i=1;sqrt(n*i)<m;i++){
		int k=sqrt(n*i);
		if(k*k==n*i&&k<m)re+=i;
	}
	return re;
 }
 int main(){
	calc(384,12);
	printf("\n%d ",calc2(7,42));
 }







*問い2-3
24a=90b=c^2を満たすcを求めよ。

 #include<stdio.h>
 #include<map>
 #include<math.h>
 
 std::map<int,int> yakusuuCount(int n){
	std::map<int,int> re;
	for(int i=2;i*i<=n;i++){
		int count=0;
		while(n%i==0){
			n/=i;
			count++;
		}
		if(count>0)re[i]=count;
	}
	if(n!=1)re[n]=1;
	return re;
 }
 int calc(int n,int m){
	std::map<int,int> m1,m2;
	std::map<int,int>::iterator it;
	m1=yakusuuCount(n);
	m2=yakusuuCount(m);
	for(it=m2.begin();it!=m2.end();it++){
		int p=(*it).first;
		int p2=(*it).second;
		if(m1.find(p)==m1.end()||m1[p]<p2){
			m1[p]=p2;
		}
	}
	int c=1;
	for(it=m1.begin();it!=m1.end();it++){
		int p=(*it).first;
		int p2=(*it).second;
		if(p2%2==1)p2++;
		c*=pow(p,p2/2);
	}
	return c;
 }
 int main(){
	printf("%d",calc(24,90));
 }











*問い2-4
n^2/1250,n^3/45,n^4/768の全てが整数となる最小のnを求めよ。

 #include<stdio.h>
 #include<map>
 #include<math.h>
 std::map<int,int> yakusuuCount(int n){
	std::map<int,int> re;
	for(int i=2;i*i<=n;i++){
		int count=0;
		while(n%i==0){
			n/=i;
			count++;
		}
		if(count>0)re[i]=count;
	}
	if(n!=1)re[n]=1;
	return re;
 }
 void calc2(std::map<int,int> m,std::map<int,int>& re,int n){
	std::map<int,int>::iterator it;
	for(it=m.begin();it!=m.end();it++){
		int p=(*it).first;
		int p2=((*it).second-1)/n+1;
		if(re.find(p)==re.end()||re[p]<p2){
			re[p]=p2;
		}
	}
 }
 int calc(int a,int b,int c){
	std::map<int,int> m1,m2,m3,ans;
	std::map<int,int>::iterator it;
	m1=yakusuuCount(a);
	m2=yakusuuCount(b);
	m3=yakusuuCount(c);
	calc2(m1,ans,2);
	calc2(m2,ans,3);
	calc2(m3,ans,4);
	int re=1;
	for(it=ans.begin();it!=ans.end();it++){
		re*=pow((*it).first,(*it).second);
	}
	return re;
 }
 int main(){
	printf("%d",calc(1250,45,768));
 }





*問い2-5
100!は何個の2で割り切れるか、また末尾に何個0が並ぶか。

 #include<stdio.h>
 int main(){
	int count5=0,count2=0;
	for(int i=1;i<=100;i++){
		int n=i;
		while(n%2==0){
			n/=2;
			count2++;
		}
		while(n%5==0){
			n/=5;
			count5++;
		}
	}
	printf("%d %d",count2,count5);
 }