「オイラープロジェクト351~360」の編集履歴(バックアップ)一覧はこちら
「オイラープロジェクト351~360」(2012/11/24 (土) 17:20:11) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い351
http://projecteuler.net/problem=351
*解法
この問題は点をベクトルA(1,0),ベクトルB(cos60,sin60)とすると全部の点を
tA+sBとして表現できます。
となればtとsが約分できる点は他の点に遮られている点となります。
約分できる数の個数となればファイ関数の出番です。
n-φ(n)とすれば遮られた点の個数が出ます。
0度<Θ<60度の範囲だけ求めれば後は対象なので6倍します。
ちょっとした注意点として計算を簡単にするために原点からX軸と60度、120度、、300度の角度にある点は別口で計算しています。
早解きを目指したので計算部分のコードに少し混乱が見られますがまあ正しい答えを出すのでいいかと。
#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;
}
*問い351
http://projecteuler.net/problem=351
*解法
この問題は点をベクトルA(1,0),ベクトルB(cos60,sin60)とすると全部の点を
tA+sBとして表現できます。
となればtとsが約分できる点は他の点に遮られている点となります。
約分できる数の個数となればファイ関数の出番です。
n-φ(n)とすれば遮られた点の個数が出ます。
0度<Θ<60度の範囲だけ求めれば後は対象なので6倍します。
ちょっとした注意点として計算を簡単にするために原点からX軸と60度、120度、、300度の角度にある点は別口で計算しています。
早解きを目指したので計算部分のコードに少し混乱が見られますがまあ正しい答えを出すのでいいかと。
コード実行時間3分30秒。
人生で三冊目の整数論の本を買った効果でてます。
#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;
}