首页 > 代码库 > HDU 3501 Calculation 2
HDU 3501 Calculation 2
题目大意:求小于n的与n不互质的数的和。
题解:首先欧拉函数可以求出小于n的与n互质的数的个数,然后我们可以发现这样一个性质,当x与n互质时,n-x与n互质,那么所有小于n与n互质的数总是可以两两配对使其和为n,这也就是为什么当n大于2时欧拉函数都是偶数,知道这一点后,就可以计算出小于n与n互质的数的和了,那么不互质的和只要用总和来减就可以了。
#include <cstdio>typedef long long LL;LL n,ans;LL Eular(LL n){ LL ret=1; for(int i=2;i*i<=n;i++){ if(n%i==0){ n/=i,ret*=(i-1); while(n%i==0)n/=i,ret*=i; } } if(n>1)ret*=(n-1); return ret;}int main(){ while(~scanf("%lld",&n)&&n){ ans=n*(n+1)/2-n; ans-=Eular(n)*n/2; printf("%lld\n",ans%1000000007); }return 0;}
HDU 3501 Calculation 2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。