【数论-欧拉函数】HDU 3501 Calculation 2 （ 与n不互质的数的和 ）

【数论-欧拉函数】HDU 3501 Calculation 2 （ 与n不互质的数的和 ）

【题目链接】​​click here~​​

【题目大意】给定整数n，求与n不互质的数的和，最后mod1e9+7

【解题思路】我们利用欧拉函数和欧几里德定理，if  gcd(n,i)==1 ，则有 gcd(n,n-i)==1 ，可以知道 其中一个若为i则存在一个为n-i 那么二者之和为n  ，这样的一共有eular(n)/2对  故与n互质的所有数的和为 n*eular(n)/2 那么与n不互质的 数就是(n)*(n-1)/2-n*eular(n)/2 【source】​​​ 2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT ​​

代码：

#include using namespace std;const int mod=1e9+7;typedef __int64 lint;lint eular(lint n){ int res=1; for(int i=2;i*i<=n;i++){ if(n%i==0){ n/=i,res*=i-1; while(n%i==0) n/=i,res*=i; } } if(n>1) res*=n-1; return res;}int main(){ lint n,res; while(scanf("%I64d",&n)!=EOF){ if(!n) break; res=((n)*(n-1)/2-n*eular(n)/2)%mod; printf("%I64d\n",res%mod); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。