首页 > 代码库 > 【数论】【筛法求素数】【欧拉函数】bzoj2818 Gcd
【数论】【筛法求素数】【欧拉函数】bzoj2818 Gcd
gcd(x,y)(1<=x,y<=n)为素数(暂且把(x,y)和(y,x)算一种) 的个数
<=> gcd(x/k,y/k)=1，k是x的质因数 的个数
<=> Σφ(x/k) (1<=x<=n,k是x的质因子)
这样的复杂度无法接受，
∴我们可以考虑枚举k，计算Σφ(q/k) (k是n以内的质数，q是n以内k的倍数)，即Σ[φ(1)+φ(2)+φ(3)+...+φ(p)] (p=n/k)
介个phi的前缀和可以预处理粗来。
但是(x,y)和(y,x)并不同，所以在计算前缀和的时候，对于φ(x) (x≠1)，要乘2再累加，即Σ[φ(1)+φ(2)*2+φ(3)*2+...+φ(p)*2] (p=n/k)。
∴对每个n以内的素数，我们可以O(1)地得到其对答案的贡献。
∴时间复杂度花费在筛素数和预处理phi上，为O(n*log(log(n)))或O(n)[线性筛]。
1 #include<cstdio> 2 using namespace std; 3 typedef long long ll; 4 int phi[10000001],n; 5 bool unPrime[10000001]; 6 ll ans,sum[10000001]; 7 void Shai_Prime() 8 { 9 unPrime[1]=1;10 for(ll i=2;i<=n;i++) if(!unPrime[i])11 {12 ans+=sum[n/i];13 for(ll j=i*i;j<=n;j+=i)14 unPrime[j]=1;15 }16 }17 void phi_table()18 {19 phi[1]=1;//规定phi(1)=1; 20 for(int i=2;i<=n;i++)21 if(!phi[i])//若i是质数(类似筛法的思想) 22 for(int j=i;j<=n;j+=i)//i一定是j的质因数 23 {24 if(!phi[j]) phi[j]=j;25 phi[j]=phi[j]/i*(i-1);26 }27 }28 void init_sum()29 {30 sum[1]=phi[1];31 for(int i=2;i<=n;i++) sum[i]=(ll)(phi[i]<<1)+sum[i-1];32 }33 int main()34 {35 scanf("%d",&n); phi_table(); init_sum(); Shai_Prime();36 printf("%lld\n",ans);37 return 0;38 }
【数论】【筛法求素数】【欧拉函数】bzoj2818 Gcd
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。