51nod 1040 最大公约数之和

Type:欧拉函数,gcd性质,思维

题目

给出一个n,求1-n这n个数,同n的最大公约数的和。比如:n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6,加在一起 = 15

Input

1个数N(N <= 10^9)

Output

公约数之和

Input示例

6

Output示例

15

题解

N<=10^9,所以肯定无法暴力枚举
考虑我们要求 lambda(gcd(i,N) | i∈[1,N])

我们可以知道:
对于每个数N,他的约数范围在[1~N]之间,即我们可以将问题转化为(设约数为Ni,1~N中约数为Ni个数为Mi):

lambda(Ni*Mi)

假设我们已经得到了Ni,问题就在于我们如何求出Mi
设i为1~N中任意数:

(1) Mi=count(gcd(i,N)=Ni | i∈[1~N])
=count(gcd(i/Ni,N/Ni)=1 | i∈[1~N])

即我们只需要求出1~N中与N/Ni互素的数的个数即可

即 euler(N/Ni)

(2) Mi=euler(N/Ni)

ans=lambda(Ni*euler(N/Ni))

然后有一个小性质,即 i*i<=N时,我们枚举到sqrt(i)同时求出 N/i ,枚举完所有的 i 即枚举完所有 1~N 内 N 的约数.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N;

LL euler(LL n){
    LL res=n,a=n;
    for(LL i=2;i*i<=a;++i){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0)a/=i;
        }
    }
    if(a>1)res=res/a*(a-1);
    return res;
}

int main(){
    while(~scanf("%lld",&N)){
        LL ans=0;
        for(LL i=1;i*i<=N;++i){
            if(N%i==0){
                ans+=(i*euler(N/i));
                if(i*i!=N){
                    ans+=((N/i)*euler(i));
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

POJ 3090

Link

https://vjudge.net/problem/POJ-3090

Type: 欧拉函数

题意

第一象限的点(x,y),给定一个N,问你,(0,0)~(N,N)范围中有多少连接原点且连线上没有整数坐标的点?

题解

想到如果两个数互质,则他与原点的连线上,必然没有整数点.

然后原题转换成该范围内有多少个点的 x与y互质

这个与poj2478这道题求法一样,有一点不同的是,(x,y)存在的同时也会存在(y,x) 并且会同时存在(1,0)(0,1)(1,1)这三个点,所以答案是

Farey[n]*2+3

Code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000+100;
int phi[maxn];
int Farey[maxn];


inline void phi_table(){
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]-phi[j]/i;
            }
        }
    }
}

inline void init(){
    phi_table();
    memset(Farey,0,sizeof(Farey));
    for(int i=2;i<maxn;++i){
        Farey[i]=Farey[i-1]+phi[i];
    }
}

int main(){
    init();
    int n,kase=1,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%d %d %d\n",kase++,n,Farey[n]*2+3);
    }
    return 0;
}

POJ 2478

Link

https://vjudge.net/problem/POJ-2478

Type: 欧拉函数

题意

F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}

其中分子与分母互质.

目标是求Fn中的最简分数有多少个

题解

仔细观察会发现因为所有分数分子分母都是互素的
设n为分母,相同分母n的最简分数的个数就等于与n互质的数的个数.
分母从2开始计数

答案就是2~n的phi(k)的和

注意和斐波那契一样,Farey序列也会超过long long

Code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000000+100;
LL phi[maxn];
LL Farey[maxn];


inline void phi_table(){
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(LL i=2;i<maxn;++i){
        if(!phi[i]){
            for(LL j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]-phi[j]/i;
            }
        }
    }
}

inline void init(){
    phi_table();
    memset(Farey,0,sizeof(Farey));
    for(int i=2;i<maxn;++i){
        Farey[i]=Farey[i-1]+phi[i];
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n)&&n){
        printf("%lld\n",Farey[n]);
    }
    return 0;
}

POJ 2407

Link

https://vjudge.net/problem/POJ-2407

Type: 欧拉函数

题意

求小于n 且与n互质的数的个数

题解

简单欧拉,但因为是十亿的数据量,所以不能预处理

Code

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

int phi(int n){
    int ans=n;
    for(int i=2;i*i<=n;++i){
        if(n%i==0){
            ans=ans-ans/i;
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1){
        ans=ans-ans/n;
    }
    return ans;
}

int main(){
    int n;
    while(cin>>n&&n){
        cout<<phi(n)<<endl;
    }
    return 0;
}

UVa 11426

Link

https://vjudge.net/problem/UVA-11426

Type: 数论,欧拉函数,递推,思维

题意

输入正整数n,求gcd(1,2)+gcd(1,3)+gcd(2,3)+gcd(1,4)+…+gcd(n-1,n)

保证输出不超过long long

范围: n∈[1,4000000]

题解

首先我们应该清楚

4000000的数据,用暴力 – 对每个gcd求值相加复杂度是i*j*O(gcd) 你懂就行,这么大的复杂度肯定爆炸.

所以我们第一想法肯定是预处理.

我们设 f(n) 为 (1,n)+(2,n)+(3,n)+…+(n-1,n)
则 S(n)=f(1)+f(2)+…+f(n)

通过这个公式我们就可以递推出所有的 S(n)

S(n)=S(n-1)+f(n)

然后我们的问题就转化成了求f(n)

首先我们会自然地想到,与n互素的答案是1.即(k,n)的结果都是n的约数

我们可以按照这个约数来进行分类,

用 g(n,i)表示满足gcd(x,n)=i 且 x\<n 的正整数x的个数
则: f(n)=Sum(i*g(n,i) | i是n的约数,g(n,i)是1~n中gcd(k,n)=i的k的个数)

然后我们注意到:
-gcd(x,n)=i
-则gcd(x/i,n/i)=1
-即x/i与n/i互质

然后我们就可以将 g(n,i) 看做1~n中与 n/i 互质的数的个数,即

g(n,i) = phi(n/i)

然后我们预处理phi[maxn],预处理完以后处理f(n),这里如果用二重循环依然是接受不了的

所以我们沿用筛法的思想对f[maxn]数组进行预处理,遇到i 是 k 的约数时,直接f[k]+=(i*phi[n/i])

最后预处理S[maxn]即可

Code

/*
我们要求:
G=Sigma(i=1~N) Sigma(j=i+1~N) GCD(i,j)
N<=4000000,这样的范围二次循环+GCD肯定是不行的
所以我们考虑
f(n)=Sigma(i=1~n-1) gcd(i,n)
则
G(n)=Sigma(i=1~n) f(i)
=G(n-1)+f(n)
所以我们的问题转换为如何求f(n)

即k都是n的约数
可以按照约数进行分类,用g(n,i)表示满足 (x,n)=i且x<n的正整数x的个数
则 f(n)=sum(i\*g(n,i)|i是n的约数)

再重提: g(n,i)代表满足(x,n)=i,且x<n的正整数x的个数

我们知道,如果 (a,n)=k
则 (a/k,n/k)=1

所以我们可以理解为g(n,i)代表的是x/i与n/i互质的数的个数
即满足条件的x/i 有 phi(n/i)个
g(n,i)=phi(n/i)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=4000000+10;
LL phi[maxn];

LL f[maxn];

LL g[maxn];
void phi_table(){
    for(int i=2;i<maxn;++i) phi[i]=0;
    phi[1]=1;
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}

void init(){
    phi_table();
    memset(f,0,sizeof(f));
    for(int i=1;i<maxn;++i){
        for(int j=i*2;j<maxn;j+=i){
            f[j]+=(i*phi[j/i]);
        }
    }
    memset(g,0,sizeof(g));
    for(int i=1;i<maxn;++i) g[i]=g[i-1]+f[i];
}

int main(){
    init();
    int k;
    while(~scanf("%d",&k) && k){
        printf("%lld\n",g[k]);
    }
    return 0;
}

HDU 2588 GCD

类型: 数论-欧拉函数-折半枚举

原题连接: https://vjudge.net/problem/HDU-2588

题意

输入N,M,对于每个 X (1=<X<=N)判断是否 GCD(X,N)>=M,输出有多少这样的X.

题解

首先无法枚举X求GCD(X,N)

我们考虑 (X,N) = (q*d,b*d) 其中d是X,N的最大公约数. 可以知道 b>=q 且 b与q互质①. 所以就转换成了对每个这样的d求 euler(b)(见①) 且 d>=M 的个数.

也就转换成了枚举d求euler(b)之和.但是这仍是O(TNlgN)复杂度的.

所以我们采用折半枚举的做法,因为要枚举的是d,而d*b在sqrt(N)之后就变成了b*d了.所以我们可以只需要枚举sqrt(N)个数,将b,d都看做b即可.

Code:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int euler(int n){
    int res=n,a=n;
    for(int i=2;i*i<=a;++i){
        if(a%i==0){
            ///φ(N)=N*(1-1/P1)*(1-1/P2)...其中P是素因子
            res=res/i*(i-1);//先进行除法方为了预防溢出
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;++i){
        int ans=0;
        int N,M;
        scanf("%d%d",&N,&M);
        for(int i=1;i*i<=N;++i){
            if(N%i==0){
                if(i>=M)
                    ans+=euler(N/i);
                if((N/i)!=i && (N/i)>=M)
                ///如果==i且>=M的话证明i>=M,而不需要计算两次,所以排除掉
                    ans+=euler(i);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

AOJ NTL_1_D Euler’s Phi Function & 欧拉函数相关

欧拉函数: 提供1到N中与N互质的数的个数.

定义和简单性质

欧拉函数用希腊字母φ(Phi)表示,φ(N)表示N的欧拉函数.

对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1).

性质

1.对于素数p,φ(p)=p-1,对于两个素数p,q φ(pq)=(p-1)*(q-1)

欧拉函数是积性函数,但不是完全积性函数.

证明:

函数的积性即:
若m,n互质,则φ(mn)=φ(m)φ(n).由“m,n互质”可知m,n无公因数,所以:
φ(m)φ(n)=m(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)·n(1-1/p1′)(1-1/p2′)(1-1/p3′)…(1-1/pn’)
其中p1,p2,p3…pn为m的质因数,p1′,p2′,p3’…pn’为n的质因数,而m,n无公因数,所以:
p1,p2,p3…pn,p1′,p2′,p3’…pn’
互不相同,所以:
p1,p2,p3…pn,p1′,p2′,p3’…pn’
均为mn的质因数且为mn质因数的全集,所以:
φ(mn)=mn(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)(1-1/p1′)(1-1/p2′)(1-1/p3′)…(1-1/pn’)
所以:
φ(mn)=φ(m)φ(n).

即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立(n与m互质).

2.对于一个正整数N的素数幂分解N=P1^q1P2^q2…*Pn^qn.

则 φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

3.除了N=2,φ(N)都是偶数.

4.设N为正整数,∑φ(d)=N (d|N)(d是N的质因数).

根据性质二,我们可以在O(sqrt(n))的时间内暴力求出一个数的欧拉函数值.

如果我们要求1000000以内所有数的欧拉函数,怎么办.

上面的方法复杂度将高达O(N*sqrt(N)).

暴力方法:

#include<iostream>
#include<algorithm>
using namespace std;

///返回euler(n)
int euler(int n){
    int res=n,a=n;
    for(int i=2;i*i<=a;++i){
        if(a%i==0){
            ///φ(N)=N*(1-1/P1)*(1-1/P2)...其中P是素因子
            res=res/i*(i-1);//先进行除法方为了预防溢出
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

int main(){
    int a[10]={2,10,100,1000,5,7,9,11,12,13};
    for(int i=0;i<10;++i)
        cout<<euler(a[i])<<endl;
    return 0;
}

结果:

我们可以将这个方法和筛法求素数的想法结合,试用筛法求出1~n内各个数字的euler(n).

φ(n)=n(1-1/p1)(1-1/p2)….(1-1/pk)
其中p1、p2…pk为n的所有素因子(这个素因子是由整数素分得来的)。
比如:φ(12)=12
(1-1/2)(1-1/3)=4。

比如求10以内所有数的φ值:

1.设一数组phi[11],赋初值phi[1]=1,phi[2]=2…phi[10]=10

2.然后从2开始循环

把2的倍数的φ值(1-1/2),则phi[2]=21/2=1,phi[4]=41/2=2,phi[6]=61/2=3….;

再是3,3的倍数的φ值(1-1/3),则phi[3]=32/3=2,phi[6]=3*2/3=2,phi[9]=…..;

再5,再7…因为对每个素数都进行如此操作,因此任何一个n都得到了φ(n)=n*(1-1/p1)(1-1/p2)….(1-1/pk)的运算

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;

///筛法求euler(1)~euler(n)
const int maxn=101;
int euler_1_n[maxn];

void a_euler(){
    euler_1_n[1]=1;
    for(int i=2;i<maxn;++i) euler_1_n[i]=i;
    for(int i=2;i<maxn;++i){
        if(euler_1_n[i]==i){
            for(int j=i;j<maxn;j+=i){
                euler_1_n[j]=euler_1_n[j]/i*(i-1);
            }
        }
    }
}

int main(){
    a_euler();
    for(int i=1;i<101;++i)
        cout<<euler_1_n[i]<<endl;

    return 0;
}

AOJ NTL_1_D Euler’s Phi Function

这道题数值范围是1e10,没超过int.而且只需要求一个数的euler.
O(lgn)暴力即可.

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

///返回euler(n)
int euler(int n){
    int res=n,a=n;
    for(int i=2;i*i<=a;++i){
        if(a%i==0){
            ///φ(N)=N*(1-1/P1)*(1-1/P2)...其中P是素因子
            res=res/i*(i-1);//先进行除法方为了预防溢出
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

int main(){
    int n;
    cin>>n;
    cout<<euler(n)<<endl;

    return 0;
}

UVa 10820

【类型】

欧拉函数值,素数筛法,打表

【题目来源】

算法竞赛入门 P322 例题10-7

UVa-10820-Send a Table

【思路】

运用素数筛法的思想对1~50000内的数打表得到每个数的欧拉phi函数值.

然后处理表,使得从3开始往后每个phi[i]都等于前面的phi[i]的和加上phi[i].

题目说可以通过f(x,y)计算f(xk,yk)即其意思就是要求的表内x,y必须互素.

其答案是2*f(n)+1,特判n=1.

【Code】

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int phi[50010]={0};

void init(){
    int n=50003;
    for(int i=2;i<=n;++i) phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;++i)
        if(!phi[i])
            for(int j=i;j<=n;j+=i){
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
    for(int i=3;i<=n;++i)
        phi[i]+=phi[i-1];
}

int main(){
    init();
    int M;
    while(scanf("%d",&M),M){
        M==1?printf("1\n"):printf("%d\n",2*phi[M]+1);
    }
    return 0;
}