Bzoj-2218 Gcdオラ関数
20973 ワード
テーマリンク:http://www.lydsy.com/JudgeOnline/problem.php?id=2818
与えられた整数Nは、1<=x,y<=Nであり、Gcd(x,y)が素数の対(x,y)の数を求める.
実は一つの転化問題です.gcd(x,y)=k、1<=x,y==nの対数はgcd(x,y)=1、<=x,y==n/kの対数を求めることに等しいです.じゃ、次は各素数k＝preme[i]を列挙してから、オラ関数を使って求めることができます.Σ(2＊Σ(phi[n/preme[i])-1).ここではnが大きいので、直接的にEuler関数の表を求めて、線形ふるい法が必要です.私の以前のphitableテンプレートは O(Σp<这里>で詳しく紹介されています.以下の通り抜粋します
次のコードは、Eula関数を計算する線形ふるいの素数です.コードの原型の起源はすでに考証することができなくて、1つの合理的な推測を作り出して、あるがOIあるいはACM/ICPCの神牛をやって初めて書きました.の各数は少なくとも一回 にアクセスされます.の各数は最大一回 に訪問されます.
各数は少なくとも一回アクセスされます.
素数については、必ず
合数については、各合数は最小の素数ともう一つの数の積として表すことができますが、他のすべての数(つまり
各数はせいぜい一回まで訪問されます.
素数については、
合数については、
証明済み
以上のように、各数は一回訪問され、一回だけ訪問されます.したがって、アルゴリズム全体の複雑さは
——————————————————私は分割線です——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
主にデリバリー最適化を使用しました.
i%preme[j]なら、phi[i]preme[j]=n(p 1-1)/p 1*…(pn-1)/pn*(preme[j]-1)/preme[j]*preme[j]=phi[i]*(preme[j]-1)
そうでなければ:phi[i*preme[j]=n(p 1-1)/p 1*…(pn-1)/pn*preme[j]=phi[i]*(preme[j]-1)
与えられた整数Nは、1<=x,y<=Nであり、Gcd(x,y)が素数の対(x,y)の数を求める.
実は一つの転化問題です.gcd(x,y)=k、1<=x,y==nの対数はgcd(x,y)=1、<=x,y==n/kの対数を求めることに等しいです.じゃ、次は各素数k＝preme[i]を列挙してから、オラ関数を使って求めることができます.Σ(2＊Σ(phi[n/preme[i])-1).ここではnが大きいので、直接的にEuler関数の表を求めて、線形ふるい法が必要です.私の以前のphitableテンプレートは O(Σp
次のコードは、Eula関数を計算する線形ふるいの素数です.コードの原型の起源はすでに考証することができなくて、1つの合理的な推測を作り出して、あるがOIあるいはACM/ICPCの神牛をやって初めて書きました.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool com[MAXN]; int primes, prime[MAXN], phi[MAXN]; phi[1] = 1; for (int i = 2; i <= n; ++i) { if (!com[i]) { prime[primes++] = i; phi[i] = i-1; } for (int j = 0; j < primes && i*prime[j] <= n; ++j) { com[i*prime[j]] = true; if (i % prime[j]) phi[i*prime[j]] = phi[i]*(prime[j]-1); else { phi[i*prime[j]] = phi[i]*prime[j]; break; } } } if (i % prime[j] == 0) break;各数は少なくとも一回アクセスされます.
素数については、必ず
iのループにアクセスし、素数として決定する.合数については、各合数は最小の素数ともう一つの数の積として表すことができますが、他のすべての数(つまり
i)を列挙しましたので、必ず最小の素数によってふるい落とされます.各数はせいぜい一回まで訪問されます.
素数については、
jのサイクルにおいてアクセスすることはできないので、iのサイクルにおいては、ちょうど一回だけアクセスされる.合数については、
i = i1 = p * aにおいて、i1 % prime[j1] == 0においてbreakがあるので、x = i1 * prime[k] = p * a * prime[k] (k > j1)において1回ふるい落とされたり、i = i1, j = kによってi = a * prime[k]によってふるい落とされたりすることはあり得ない.証明済み
以上のように、各数は一回訪問され、一回だけ訪問されます.したがって、アルゴリズム全体の複雑さは
pである.——————————————————私は分割線です——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
主にデリバリー最適化を使用しました.
i%preme[j]なら、phi[i]preme[j]=n(p 1-1)/p 1*…(pn-1)/pn*(preme[j]-1)/preme[j]*preme[j]=phi[i]*(preme[j]-1)
そうでなければ:phi[i*preme[j]=n(p 1-1)/p 1*…(pn-1)/pn*preme[j]=phi[i]*(preme[j]-1)
1 //STATUS:C++_AC_856MS_118460KB
2 #include <functional>
3 #include <algorithm>
4 #include <iostream>
5 //#include <ext/rope>
6 #include <fstream>
7 #include <sstream>
8 #include <iomanip>
9 #include <numeric>
10 #include <cstring>
11 #include <cassert>
12 #include <cstdio>
13 #include <string>
14 #include <vector>
15 #include <bitset>
16 #include <queue>
17 #include <stack>
18 #include <cmath>
19 #include <ctime>
20 #include <list>
21 #include <set>
22 #include <map>
23 using namespace std;
24 //#pragma comment(linker,"/STACK:102400000,102400000")
25 //using namespace __gnu_cxx;
26 //define
27 #define pii pair<int,int>
28 #define mem(a,b) memset(a,b,sizeof(a))
29 #define lson l,mid,rt<<1
30 #define rson mid+1,r,rt<<1|1
31 #define PI acos(-1.0)
32 //typedef
33 typedef long long LL;
34 typedef unsigned long long ULL;
35 //const
36 const int N=10000010;
37 const int INF=0x3f3f3f3f;
38 const int MOD=100000,STA=8000010;
39 const LL LNF=1LL<<60;
40 const double EPS=1e-8;
41 const double OO=1e15;
42 const int dx[4]={-1,0,1,0};
43 const int dy[4]={0,1,0,-1};
44 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
45 //Daily Use ...
46 inline int sign(double x){return (x>EPS)-(x<-EPS);}
47 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
48 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
49 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
50 template<class T> inline T Min(T a,T b){return a<b?a:b;}
51 template<class T> inline T Max(T a,T b){return a>b?a:b;}
52 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
53 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
54 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
55 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
56 //
57
58 LL phi[N];
59 int prime[N];
60 int cnt;
61
62 void phi_and_prime_table(int n)
63 {
64 int i,j;
65 cnt=0;phi[1]=1;
66 for(i=2;i<=n;i++){
67 if(!phi[i]){
68 prime[cnt++]=i;
69 phi[i]=i-1;
70 }
71 for(j=0;j<cnt && i*prime[j]<=n;j++){
72 if(i%prime[j])
73 phi[i*prime[j]]=phi[i]*(prime[j]-1);
74 else {phi[i*prime[j]]=phi[i]*prime[j];break;}
75 }
76 }
77 }
78
79 int n;
80
81 int main(){
82 // freopen("in.txt","r",stdin);
83 int i,j;
84 LL ans;
85 scanf("%d",&n);
86 cnt=0;
87 phi_and_prime_table(n);
88 for(i=2;i<=n/2;i++)phi[i]+=phi[i-1];
89 ans=0;
90 for(i=0;i<cnt;i++){
91 ans+=(phi[n/prime[i]]<<1)-1;
92 }
93 printf("%lld
",ans);
94 return 0;
95 }