[HDU3501]Calculation 2 (欧拉函数)

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


本文章由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