Longge的问题

给定正整数，求
${\sum }_{i=1}^{n}gcd(i,n)$∑i=1n​gcd(i,n)
n<=2^32

枚举gcd:
${\sum }_{i=1}^{n}gcd(i,n)={\sum }_{d\mid n}d{\sum }_{i=1}^n\left[gcd\right(i,n)=d]$∑i=1n​gcd(i,n)=∑d∣n​d∑i=1n​[gcd(i,n)=d]
= ${\sum }_{d\mid n}d{\sum }_{i=1}^{n/d}\left[gcd\right(i,n/d)=1]$∑d∣n​d∑i=1n/d​[gcd(i,n/d)=1]
= ${\sum }_{d\mid n}d\ast phi\left(n/d\right)$∑d∣n​d∗phi(n/d)

枚举n的约数可以直接求