[HDU3501]Calculation 2 (欧拉函数)

发布于 2018-01-11  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU3501]Calculation 2 (欧拉函数)

HDU 3501 Calculation 2

Description

Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.

Http

https://vjudge.net/problem/HDU-3501

Tag

欧拉函数

题目大意

求\(\sum_{i=1}^{n} [gcd(i,n)!=1]*i\)

解决思路

考虑若有\(gcd(i,n)==1\),那一定会有gcd(n-i,n)==1,那么可以知道,与一个数互质的数一定是一组一组出现的,所以可以知道与N互质的数的和就是N*\phi(N)/2。那么根据补集原理,用1~N的和减去与N互质的数之和就是与N不互质的数之和啦。
注意特判1。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU3501]Calculation 2 (欧拉函数)


HNCJ OIer 一枚