「オイラープロジェクト231～240」の編集履歴（バックアップ）一覧はこちら

「オイラープロジェクト231～240」(2012/11/11 (日) 16:54:01) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*Problem 231 「二項係数の素因数分解」 †
二項係数 10C3 = 120 は
120 = 23 × 3 × 5 = 2 × 2 × 2 × 3 × 5, 2 + 2 + 2 + 3 + 5 = 14 を満たす. 
つまり, 10C3 を素因数分解した項の和は 14 となる.
20000000C15000000を素因数分解した項の和を求めよ.

解法
素因数分解の一意性を利用して解いてみました。
2000万！/(1500万!*500万！)で2000万と1500万と５００万を素因数から構成しています。
手元のパソコンで30秒で答えが出ますが、私の場合整数論に関する授業を人生で一度も受けたことがないので解き方は基本全部自分で考えついた我流となっています。
おそらく効率が悪いコードでみる人からみたら失笑ものコードだと思います。
精進するしかありません。


 #include<stdio.h>
 #include<iostream>
 const int size=6000*1000;
 int memo[size+1]={0};
 void calc(){
	__int64 a,n,sum=0,t,t2000,t1500,t500;
	for(n=2;n<=2000*10000;n++){
		a=n;
		t=0;
		for(int i=2;i*i<=a;i+=1+(i&1)){
			while(a%i==0){
				t+=i;
				a/=i;
				if(size>a){
					t+=memo[(int)a];
					a=1;
					break;
				}
			}
			if(a==1)break;
		}
		if(a!=1)t+=a;
		if(size>n)memo[(int)n]=t;
		sum+=t;
		if(n%1000000==0)std::cout<<n<<" "<<sum<<"\n";
		if(n==2000*10000)t2000=sum;
		if(n==1500*10000)t1500=sum;
		if(n== 500*10000)t500=sum;
	}
	std::cout<<t2000<<" "<<t1500<<" "<<t500<<"\n";
	std::cout<<t2000-t1500-t500<<"\n";
 }
 int main(){
	calc();
 }

*Problem 231 「二項係数の素因数分解」 †
二項係数 10C3 = 120 は
120 = 23 × 3 × 5 = 2 × 2 × 2 × 3 × 5, 2 + 2 + 2 + 3 + 5 = 14 を満たす. 
つまり, 10C3 を素因数分解した項の和は 14 となる.
20000000C15000000を素因数分解した項の和を求めよ.

解法
素因数分解の一意性を利用して解いてみました。
2000万！/(1500万!*500万！)で2000万と1500万と５００万を素因数から構成して差分を引けば答えが出ます。
手元のパソコンで30秒で答えが出ますが、私の場合整数論に関する授業を人生で一度も受けたことがないので解き方は基本全部自分で考えついた我流となっています。
おそらく効率が悪いコードでみる人からみたら失笑ものコードだと思います。
精進するしかありません。


 #include<stdio.h>
 #include<iostream>
 const int size=6000*1000;
 int memo[size+1]={0};
 void calc(){
	__int64 a,n,sum=0,t,t2000,t1500,t500;
	for(n=2;n<=2000*10000;n++){
		a=n;
		t=0;
		for(int i=2;i*i<=a;i+=1+(i&1)){
			while(a%i==0){
				t+=i;
				a/=i;
				if(size>a){
					t+=memo[(int)a];
					a=1;
					break;
				}
			}
			if(a==1)break;
		}
		if(a!=1)t+=a;
		if(size>n)memo[(int)n]=t;
		sum+=t;
		if(n%1000000==0)std::cout<<n<<" "<<sum<<"\n";
		if(n==2000*10000)t2000=sum;
		if(n==1500*10000)t1500=sum;
		if(n== 500*10000)t500=sum;
	}
	std::cout<<t2000<<" "<<t1500<<" "<<t500<<"\n";
	std::cout<<t2000-t1500-t500<<"\n";
 }
 int main(){
	calc();
 }