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万と500万を素因数から構成して差分を引けば答えが出ます。
手元のパソコンで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();
}
最終更新:2012年11月11日 16:54