首页 > 其他 > 详细

HDOJ 3501 Calculation 2

时间:2017-04-10 22:34:55      阅读:319      评论:0      收藏:0      [点我收藏+]

题目链接

分析:

要求的是小于$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 NeighThorn
using 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

原文:http://www.cnblogs.com/neighthorn/p/6691150.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!