「オイラープロジェクト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; }

表示オプション

横に並べて表示:
変化行の前後のみ表示: