オイラープロジェクト351～360 - c21coterie @ ウィキ

問い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;
}