Menu

ProjectEuler/1-10

Last-modified: 2013-11-05 (火) 17:07:32

1

略

2 

#include

using namespace std;

int main()
{
	int ans=0;
	int tmp[3]={0,0,1};
	while(tmp[0]<4000000)
	{
		tmp[0]=tmp[1]+tmp[2];
		if(tmp[0]%2==0) ans+=tmp[0];
		tmp[1]=tmp[2];
		tmp[2]=tmp[0];
	}
	cout << ans << endl;
	return 0;
}

3 

#include

using namespace std;

const int P_MAX=775146; // sqrt(n)

bool notPrime[P_MAX];

int main()
{
	long long int n=600851475143;
	int ans=0;

	for(int i=3;i<P_MAX;i+=2){
		if(!notPrime[i]){
			for(int j=2;i*j<P_MAX;j++) notPrime[i*j]=true;
		}
	}
	while(n%2==0) n/=2;
	for(int k=3;k<P_MAX;k+=2){
		if(n%k==0){
			n=n/k;
			if(n<P_MAX && !notPrime[n]){ ans=n; break; }
		}
	}
	cout << ans << endl;
	return 0;
}

4

  • すごくテキトーでウケる 
    #include

using namespace std;

bool isPalindromic( int n ){
	const int oo = n/100000;
	if(!oo) return false;
	n=n%100000;
	const int tt = n/10000;
	n=n%10000;
	const int hh = n/1000;
	n=n%1000;
	const int h = n/100;
	n=n%100;
	const int t = n/10;
	const int o = n%10;
	return (oo==o) && (tt==t) && (hh==h);
}

int main()
{
	int ans=0;
	for(int i=999;i>=100;i--){
		for(int j=999;j>=100;j--){
			if(i*j/100000==0) break;
			if(isPalindromic(i*j)) ans=max(i*j,ans);
		}
	}
	cout << ans << endl;
	return 0;
}

5

  • 20までの素数を列挙
  • 素数tのn乗が20を超えない最大のnを求める 
    #include
#include
#include

using namespace std;

const int P_MAX = 20;
bool notPrime[P_MAX]; // indexが奇数のものしか使わない

int main(){
	int ans=1;
	vector<int> p;

	p.push_back(2);
	for(int i=3;i<P_MAX;i+=2){
		if(!notPrime[i]){
			p.push_back(i);
			for(int j=2;i*j<P_MAX;j++) notPrime[i*j]=true;
		}
	}

	for_each(p.begin(),p.end(),[&](int t){
		int pow=t;
		while(pow*t<=20) pow*=t;
		ans*=pow;
	});

	cout << ans << endl;
	return 0;
}

6

略

7

略

8

pro=pro*num[i]/num[i-5];とかやるとゼロ除算がアレ

#include
#include
#include

using namespace std;

int num[1000];

int main(){
	int ans=0,pro=1;
	char tmp;
	deque<int> q;

	for(int i=0;i<1000;i++){
		do{
			cin >> tmp;
		}while(tmp<'0' || '9'<tmp);
		num[i]=static_cast<int>(tmp-'0');
	}

	for(int i=0;i<5;i++){
		q.push_back(num[i]);
		pro*=num[i];
	}
	ans=pro;
	for(int i=5;i<1000;i++){
		q.pop_front();
		q.push_back(num[i]);
		pro=1;
		for_each(q.begin(),q.end(),[&](int t){pro*=t;});
		ans=max(pro,ans);
	}
	cout << ans << endl;

	return 0;
}

9 

#include

using namespace std;

int main(){
	int ans=0,c;
	// 0<a<333 200<b<500 334<c<600
	for(int a=1;a<333;a++){
		for(int b=a+1;b<500;b++){
			c=1000-b-a;
			if(c*c==a*a+b*b){ ans=a*b*c; break; }
		}
		if(ans)break;
	}
	cout << ans << endl;
	return 0;
}

10

略