プロジェクトオイラー問203 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20203
Problem 203 「無平方二項係数」 †
パスカルの三角形と平方数に関する問題。

nCrの定義から素因数分解して素因数の個数を数えるだけです。

#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
std::map<int,int> ms[51];
std::set<__int64> sets;


void f(int n){
	int m=n;
	for(int i=2;i<=n;i++){
		while(n%i==0){
			n/=i;
			ms[m][i]++;
		}
	}
}

void g(int n){
	std::map<int,int> memo;
	std::map<int,int>::iterator it;
	for(int i=1;i<n-1;i++){
		for(it=ms[n-i].begin();it!=ms[n-i].end();it++){
			memo[(*it).first]+=(*it).second;
		}
		for(it=ms[i].begin();it!=ms[i].end();it++){
			memo[(*it).first]-=(*it).second;
		}
		__int64 add=1;
		for(it=memo.begin();it!=memo.end();it++){
 			if((*it).second>1)add=0;
			if((*it).second==1)add*=(*it).first;
		}
		if(add>0){
			sets.insert(add);
		}
	}
}

int main(){
 	for(int i=2;i<=50;i++){
		f(i);
	}
	for(int i=3;i<=51;i++){
		g(i);
	}
	__int64 ans=1;
	for(std::set<__int64>::iterator it=sets.begin();it!=sets.end();it++){
		ans+=(*it);
	}
	std::cout<<ans<<"\n";
}