素数筛&&欧拉筛 BZOJ2818 Gcd BZOJ2190 [SDOI2008]仪仗队

折腾了一晚上很水的数论,整个人都萌萌哒

主要看了欧拉筛和素数筛的O(n)的算法

这个比那个一长串英文名的算法的优势在于没有多次计算一个数,也就是说一个数只筛了一次,主要是在%==0之后跳出实现的,具体的解释看的迷迷糊糊,特别是欧拉函数的求解

http://blog.csdn.net/lerenceray/article/details/12420725

代码如下

 1 void ES(){
 2     for(int i=2;i<n;i++){
 3         if (!pd[i]){
 4             prime[++top]=i;
 5             phi[i]=i-1;
 6         }
 7         for (int j=1;j<=top&&prime[j]*i<=n;j++){
 8             pd[prime[j]*i]=1;
 9             if (i%prime[j]==0){
10                 phi[prime[j]*i]=phi[i]*prime[j];
11                 break;
12             }
13             phi[prime[j]*i]=phi[i]*(prime[j]-1);
14         }
15     }
16 }

顺便A掉了两个数论水题

Description

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

HINT

hint

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

题解


gcd(a,b)=p 则 gcd(a/p,b/p)=1;

设 a<=b 则gcd(a,b)=phi[b](与b互质的个数)

所以只需要枚举每一个素数,每一个数(这里可以用n的前缀和来维护,记为f[n])求解出ans=Σf[n/prime[i]]*2-1(考虑a>b,并减去(1,1)之类的值)

#include<cstdio>
const int maxn=10000010;
bool pd[maxn];
long long phi[maxn],prime[maxn],top,n,ans;
void ES(){
    for(int i=2;i<n;i++){
        if (!pd[i]){
            prime[++top]=i;
            phi[i]=i-1;
        }
        for (int j=1;j<=top&&prime[j]*i<=n;j++){
            pd[prime[j]*i]=1;
            if (i%prime[j]==0){
                phi[prime[j]*i]=phi[i]*prime[j];
                break;
            }
            phi[prime[j]*i]=phi[i]*(prime[j]-1);
        }
    }
}

int main(){
    scanf("%lld",&n);
    ES();
    for(int i=1;i<n;i++) phi[i]+=phi[i-1];
    for (int i=1;i<=top;i++) ans+=phi[n/prime[i]]*2+1;
    printf("%lld",ans);
}

Description

  作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。       现在,C君希望你告诉他队伍整齐时能看到的学生人数。

Input

  共一个数N。

Output

  共一个数,即C君应看到的学生人数。

Sample Input

  4

Sample Output

  9

HINT

【数据规模和约定】   对于 100% 的数据,1 ≤ N ≤ 40000

题解

……求出phi,算算

 1 #include<cstdio>
 2 const int maxn=40010;
 3 bool pd[maxn];
 4 int phi[maxn],prime[maxn],top,n,ans;
 5 void ES(){
 6     for(int i=2;i<n;i++){
 7         if (!pd[i]){
 8             prime[++top]=i;
 9             phi[i]=i-1;
10         }
11         for (int j=1;j<=top&&prime[j]*i<=n;j++){
12             pd[prime[j]*i]=1;
13             if (i%prime[j]==0){
14                 phi[prime[j]*i]=phi[i]*prime[j];
15                 break;
16             }
17             phi[prime[j]*i]=phi[i]*(prime[j]-1);
18         }
19     }
20 }
21
22 int main(){
23     scanf("%d",&n);
24     ES();
25     for(int i=1;i<n;i++) phi[i]+=phi[i-1];
26     ans=phi[n-1]*2+3;
27     printf("%d",ans);
28 }
时间: 01-05

素数筛&&欧拉筛 BZOJ2818 Gcd BZOJ2190 [SDOI2008]仪仗队的相关文章

欧拉筛(线性筛)

素数筛,就是按照顺序把合数踢掉,剩下的是素数. 欧拉筛是一种O(n)求素数的筛法.他避免了埃拉特斯特尼筛法对同一数的多次筛除. 欧拉筛的原理是只通过数的最小质因数筛数. 先上代码: #include <cstdio> using namespace std; const int maxn=10000000; int n, m, prime[maxn], isnt_prime[maxn], tot; void get_prime(int n){ isnt_prime[0]=isnt_prime[

常见模板(欧拉筛素数,最小生成树,快排,并查集,单源最短路)

欧拉筛素数: #include<cstdio> #define maxn 10000000+10 using namespace std; int n,prime[5000001],num_prime=0,m; bool if_prime[maxn]; void euler(int limit) { for(int i=2;i<=limit;i++) { if(!if_prime[i]) prime[++num_prime]=i; for(int j=1;prime[j]*i<=l

[51NOD1181]质数中的质数(质数筛法)(欧拉筛)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1181 思路:欧拉筛出所有素数和一个数的判定,找到大于n的最小质数序号p,并且判断p是不是质数,输出这个数. 1 /* 2 ━━━━━┒ギリギリ♂ eye! 3 ┓┏┓┏┓┃キリキリ♂ mind! 4 ┛┗┛┗┛┃\○/ 5 ┓┏┓┏┓┃ / 6 ┛┗┛┗┛┃ノ) 7 ┓┏┓┏┓┃ 8 ┛┗┛┗┛┃ 9 ┓┏┓┏┓┃ 10 ┛┗┛┗┛┃ 11 ┓┏┓┏┓┃ 12

The Euler function(线性筛欧拉函数)

/* 题意:(n)表示小于n与n互质的数有多少个,给你两个数a,b让你计算a+(a+1)+(a+2)+......+b; 初步思路:暴力搞一下,打表 #放弃:打了十几分钟没打完 #改进:欧拉函数:具体证明看po主的博客 ^0^ #超时:这里直接用欧拉函数暴力搞还是不可以的,用到线性筛欧拉函数,这里总和爆int,要用long long */ #include<bits/stdc++.h> #define ll long long using namespace std; /***********

【BZOJ 2190】【SDOI 2008】仪仗队 欧拉筛

欧拉筛模板题 #include<cstdio> using namespace std; const int N=40003; int num=0,prime[N],phi[N]; bool notp[N]; inline void shai(int n){ phi[1]=1; for(int i=2;i<=n;++i){ if (!notp[i]){ prime[++num]=i; phi[i]=i-1; } for(int j=1;j<=num&&i*prime

【BZOJ2818】Gcd 欧拉筛

Description 给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对. Input 一个整数N Output 如题 Sample Input 4 Sample Output 4 HINT hint 对于样例(2,2),(2,4),(3,3),(4,2) 1<=N<=10^7 Source 湖北省队互测 题解:首先我们要求Σgcd(x,y)=p (p为素数)=> Σgcd(x/p,y/p)=1 那么我们就可以枚举p,求y/p的欧拉函数的前缀和

欧拉筛素数+求欧拉函数

线性筛法 prime记录素数,num_prime素数下标 它们保证每个合数只会被它的最小质因数筛去 a[0]=a[1]=1; for(int i=2;i<=n;i++) { if(!a[i]) prime[num_prime++]=i; for(int j=0;j<num_prime&&i*prime[j]<=n;j++) { a[i*prime[j]]=1; if(!(i%prime[j])) break; } } } 欧拉函数 是 积性函数:对于任意互质的整数a和b有

hdu (欧拉函数+容斥原理) GCD

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1695 看了别人的方法才会做 参考博客http://blog.csdn.net/shiren_Bod/article/details/5787722 题意 a,b,c,d,k五个数,a与c可看做恒为1,求在a到b中选一个数x,c到d中选一个数y,使得gcd(x,y)等于k,求x和y有多少对. 首先可以想到选取的必是k的倍数,假设是x和y倍,则x和y一定是互质的在,那么就变成了求1到b/k和1到d/k的之

BZOJ2190 [SDOI2008]仪仗队(欧拉函数)

与HDU2841大同小异. 设左下角的点为(1,1),如果(1,1)->(x,y)和(1,1)->(x',y')向量平行,那只有在前面的能被看见.然后就是求x-1.y-1不互质的数对个数. 而x或y等于1可以另外讨论一下,就是当n不等于1时就有两个,n等于1就特判一下. 那么就用欧拉函数计数了:枚举x-1,累加小于x-1与x-1互质的个数,即合法的y-1的个数:结果还要*2,因为还有一半对称的y-1>x-1的情况:此外x-1=y-1多算了一次,减去1即可. 1 #include<c