首页 > 代码库 > BZOJ2818: Gcd

BZOJ2818: Gcd

2024-08-15 08:03:50   211人阅读

传送门

算是一道比较基础的数论题，可以用莫比乌斯反演写也可以用欧拉函数写。

莫比乌斯反演

推导过程：

不妨设$f(x)$表示对于$i\in[1,N],j\in[1,N]$且$gcd(i,j)==x$，即$f(x)=\sum\limits_{i=1}^N\sum\limits_{j=1}^N[gcd(i,j)==x]$

不妨设$g(x)$表示对于$i\in[1,N],j\in[1,N]$且$gcd(i,j)==kx$则显然$g(x)=(\lfloor \frac{N}{x} \rfloor)^2$

那么显然$g(x)=\sum\limits_{k=1}^{\lfloor \frac{N}{x} \rfloor}f(k \times x)$

根据莫比乌斯反演，可以得到$f(x)=\sum\limits_{k=1}^{\lfloor \frac{N}{x} \rfloor}g(k \times x)\mu (k)$

然后线筛预处理出莫比乌斯函数就能够得到本题答案。

技术分享
 1 //BZOJ 2818 2 //by Cydiater 3 //2016.8.16 4 #include <iostream> 5 #include <cstring> 6 #include <string> 7 #include <algorithm> 8 #include <queue> 9 #include <map>10 #include <cstdio>11 #include <cstdlib>12 #include <iomanip>13 #include <ctime>14 #include <cmath>15 using namespace std;16 #define ll long long17 #define up(i,j,n)       for(ll i=j;i<=n;i++)18 #define down(i,j,n)     for(ll i=j;i>=n;i--)19 const ll MAXN=1e7+5;20 const ll LIM=10000000;21 const int oo=0x3f3f3f3f;22 inline ll read(){23       char ch=getchar();ll x=0,f=1;24       while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25       while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26       return x*f;27 }28 ll N,prime[MAXN],cnt=0,mu[MAXN],ans=0;29 bool vis[MAXN];30 namespace solution{31       void Mobius(){32             memset(vis,0,sizeof(vis));33             mu[1]=1;34             up(i,2,LIM){35                   if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}36                   up(j,1,cnt){37                         if(i*prime[j]>LIM)break;38                         vis[i*prime[j]]=1;39                         if(i%prime[j]==0){mu[i*prime[j]]=0;break;}40                         else  mu[i*prime[j]]=-mu[i];41                   }42             }43       }44       void slove(){45             up(i,1,cnt){46                   if(prime[i]>=N)break;47                   ll t=N/prime[i];48                   int pos;49                   up(j,1,t)ans+=mu[j]*(t/j)*(t/j);50             }51             cout<<ans<<endl;52       }53 }54 int main(){55       //freopen("input.in","r",stdin);56       using namespace solution;57       Mobius();N=read();58       slove();59       return 0;60 }
Mobius

 欧拉函数

换成欧拉函数就很好理解了，不给推导过程了，最后的答案是：

$ans=\sum\limits^{p_i\in Prime}(\sum\limits_{i=1}^{\lfloor \frac{N}{p_i} \rfloor} \phi (i))\times 2 -1$

技术分享
//BZOJ 2818//by Cydiater//2016.9.30#include <iostream>#include <cstdio>#include <cstring>#include <iomanip>#include <ctime>#include <map>#include <string>#include <algorithm>#include <cstdlib>#include <queue>#include <iomanip>using namespace std;#define ll long long#define up(i,j,n)        for(int i=j;i<=n;i++)#define down(i,j,n)        for(int i=j;i>=n;i--)const int MAXN=1e7+5;const int LIM=1e7;const int oo=0x3f3f3f3f;inline ll read(){    char ch=getchar();ll x=0,f=1;    while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}    ll prime[MAXN],cnt=0,phi[MAXN],N,ans=0;bool vis[MAXN];namespace solution{    void pret(){        phi[1]=1;        memset(vis,0,sizeof(vis));        up(i,2,LIM){            if(!vis[i]){prime[++cnt]=i;phi[i]=i-1;}            up(k,1,cnt){                if(prime[k]*i>LIM)break;                vis[prime[k]*i]=1;                if(i%prime[k]==0){phi[i*prime[k]]=phi[i]*prime[k];break;}                else                phi[i*prime[k]]=phi[i]*phi[prime[k]];            }        }        up(i,1,LIM)phi[i]+=phi[i-1];    }    void slove(){        up(i,1,cnt){            if(prime[i]>N)break;            ans+=phi[N/prime[i]]*2-1;        }        cout<<ans<<endl;    }}int main(){    //freopen("input.in","r",stdin);    using namespace solution;N=read();    pret();    slove();    return 0;}
Phi

 

BZOJ2818: Gcd


联系
我们