首页 > 代码库 > BZOJ2705: [SDOI2012]Longge的问题
BZOJ2705: [SDOI2012]Longge的问题
传送门
欧拉函数的简单运用，感觉用莫比乌斯反演好像也可以搞一搞？
具体的推导过程如下:
$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 }
BZOJ2705: [SDOI2012]Longge的问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。