首页 > 代码库 > BZOJ2705: [SDOI2012]Longge的问题

BZOJ2705: [SDOI2012]Longge的问题

2024-08-15 07:57:42   209人阅读

传送门

欧拉函数的简单运用，感觉用莫比乌斯反演好像也可以搞一搞？

具体的推导过程如下:

$ans=\sum\limits_{i=1}^N gcd(i,N)$

$ans=\sum\limits_{d|N}d \times f(d)$其中，$f(d)=\sum\limits_{i=1}^N[gcd(i,N)==d]=\sum\limits_{i=1}^{\lfloor \frac{N}{d} \rfloor}[gcd(i,\lfloor \frac{N}{d} \rfloor)==1]=\phi(\lfloor \frac{N}{d} \rfloor)$

最后得到$ans=\sum\limits_{d|N}d \times \phi(\sum\limits_{d|N}d \times f(d))$

其中$\phi$可以在$O(\sqrt{N})$的时间复杂度内求出

技术分享
 1 //BZOJ 2705 2 //by Cydiater 3 //2015.9.30 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue>10 #include <map>11 #include <ctime>12 #include <cmath>13 #include <cstdlib>14 #include <iomanip>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=(1<<17)+5;20 const ll LIM=1<<17;21 inline ll read(){22     char ch=getchar();ll x=0,f=1;23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}25     return x*f;26 }27 ll prime[MAXN],cnt=0,ans=0,phi[MAXN],N,M;28 bool vis[MAXN];29 namespace solution{30     ll phi(ll x){31         ll t=x;32         up(i,2,M)if(x%i==0){33             t=t/i*(i-1);34             while(x%i==0)x/=i;35         }36         if(x>1)t=t/x*(x-1);37         return t;38     }39     void slove(){40         N=read();41         M=sqrt(1.0*N);42         up(i,1,M)if(N%i==0){43             ans+=i*phi(N/i);44             if(i*i<N)ans+=N/i*phi(i);45         }46         printf("%lld\n",ans);47     }48 }49 int main(){50     //freopen("input.in","r",stdin);51     using namespace solution;52     slove();53     return 0;54 }
View Code

 

BZOJ2705: [SDOI2012]Longge的问题


联系
我们