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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20127
Problem 127 「abc-hit」 †
abc-hitに関する問題。

計算時間1秒の解
gcd(a,b)=1,gcd(a,c)=1,gcd(b,c)＝1
より
rad(abc)=rad(a)rad(b)rad(c)＜ｃ
となればrad(c)にrad(a)が小さいaから掛けてc,aが確定したのでbを算出しこれが条件を満たすか調べればＯＫ。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

int gcd ( int a, int b )
{
 int c;
  while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
} 

struct E{ 
	int n;
	int rad;
	bool operator<(const E& e1)const{
		if(rad!=e1.rad)return rad<e1.rad;
		return n<e1.n; 
	}
}; 

const int LIMIT=120000;
bool isP[LIMIT];
int rad[LIMIT];

int main(){
	memset(isP,true,sizeof(isP));
	isP[0]=isP[1]=false;
	for(int i=2;i*i<=LIMIT;i++){
		if(isP[i]==false)continue;
		for(int j=i*2;j<LIMIT;j+=i){
			isP[j]=false;
		}
	}
	rad[0]=0;
	for(int i=1;i<LIMIT;i++){
		rad[i]=1;
	}
	
	for(int i=2;i<LIMIT;i++){
		if(isP[i]==false)continue;
		for(int j=i;j<LIMIT;j+=i){
			rad[j]*=i;
		}
		
	}
	
	std::vector<E> vec;
 	for(int i=1;i<LIMIT;i++){
		E e1;
 		e1.n=i;
		e1.rad=rad[i];
		vec.push_back(e1);
	}
	std::sort(vec.begin(),vec.end());
	
	int ans=0;
	for(int c=3;c<LIMIT;c++){
		__int64 c1=rad[c];
		if(c%10000==0)printf("%d/%d\n",c,LIMIT);
		for(int i=0;i<vec.size();i++){
			__int64 c2=c1*vec[i].rad;
			if(c2>=c)break;
			int a=vec[i].n;	
			if(c-a<=a)continue;
			int b=c-a;
			
			__int64 c3=c2*rad[b];
			if(c3>=c)continue;
			if(gcd(c,a)!=1)continue;
			if(gcd(c,b)!=1)continue;
			if(gcd(a,b)!=1)continue;
			ans+=c;
			
		}
		
	}
	printf("ans=%d\n",ans);
}