首页 > 代码库 > HDOJ 3501 Calculation 2
HDOJ 3501 Calculation 2
题目链接
分析：
要求的是小于$n$的和$n$不互质的数字之和...那么我们先求出和$n$互质的数字之和，然后减一减就好了...
$\sum _{i=1}^{n} i[gcd(i,n)==1]=\frac{n\phi(n)}{2}$
考虑$gcd(n,i)=1$，那么必然有$gcd(n,n-i)=1$，然后发现如果把$gcd(n,i)=1$和$gcd(n,n-i)=1$凑到一起会出现$n$，这样的有$\frac{\phi(n)}{2}$对...
代码：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>//by NeighThornusing namespace std;const int mod=1e9+7;int n,ans;inline int phi(int n){ int x=n,m=sqrt(n); for(int i=2;i<=m;i++) if(n%i==0){ x=1LL*x/i*(i-1)%mod; while(n%i==0) n/=i; } if(n>1) x=x/n*(n-1)%mod; return x;}signed main(void){ while(scanf("%d",&n)&&n){ ans=(1LL*n*(n-1)/2)%mod; ans-=(1LL*phi(n)*n/2)%mod; if(ans<0) ans+=mod; printf("%d\n",ans); } return 0;}
By NeighThorn
HDOJ 3501 Calculation 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。