「オイラープロジェクト351～360」の編集履歴（バックアップ）一覧に戻る

オイラープロジェクト351～360 - (2012/11/24 (土) 17:20:11) のソース

*問い351
http://projecteuler.net/problem=351

*解法
この問題は点をベクトルA(1,0),ベクトルB(cos60,sin60)とすると全部の点を
tA+sBとして表現できます。

となればｔとｓが約分できる点は他の点に遮られている点となります。
約分できる数の個数となればファイ関数の出番です。
n-φ(n)とすれば遮られた点の個数が出ます。
０度<Θ<６０度の範囲だけ求めれば後は対象なので６倍します。
ちょっとした注意点として計算を簡単にするために原点からX軸と６０度、１２０度、、３００度の角度にある点は別口で計算しています。
早解きを目指したので計算部分のコードに少し混乱が見られますがまあ正しい答えを出すのでいいかと。
コード実行時間３分３０秒。
人生で三冊目の整数論の本を買った効果でてます。


 #include<stdio.h>
 #include<vector>
 #include<iostream>
 #include<time.h>
 const int up=10000;
 std::vector<int> sosuu;
 bool so[up+1];
 void setSo(){
	int i2;
	memset(so,true,sizeof(so));
	so[0]=so[1]=false;
	for(int i=4;i<=up;i+=2)so[i]=false;
	sosuu.push_back(2);
 	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
		sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<=up;j+=i2){
			so[j]=false;
		}
	}
 }
 __int64 phi(__int64 n){
	double re=n;
	for(int i=0;i<sosuu.size()&&sosuu[i]*sosuu[i]<=n;i++){
		__int64 p=sosuu[i];
		int count=0;
		while(n%p==0){
			n/=p;
			count++;
		}
		if(count>0)re*=(1-1.0/p);
	}
	if(n!=1)re*=(1-1.0/n);
	return (__int64)re+0.5;
 }
 int main(){
	double start=clock();
	setSo();
	__int64 size=10000*10000;
	
	__int64 ans=6*(size-1),t;
	for(__int64 i=2;i<=size;i++){
		t=i-phi(i)-1;
		ans+=t*6;
		if(i%10000==0)std::cout<<i<<" "<<ans<<"\n";
	}
	std::cout<<ans<<"\ntime="<<clock()-start;
 }