题目描述
for i=1 to n
for j=1 to n
sum+=gcd(i,j)
解析
给出n求sum. gcd(x,y)表示x,y的最大公约数.
直接枚举复杂度为(O(n^2))，显然无法承受。
我们需要寻找更优的算法。
首先，打表找规律，当(n=10)时，是这样的
1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 1 3 1 1 3 1 1 3 1
1 2 1 4 1 2 1 4 1 2
1 1 1 1 5 1 1 1 1 5
1 2 3 2 1 6 1 2 3 2
1 1 1 1 1 1 7 1 1 1
1 2 1 4 1 2 1 8 1 2
1 1 3 1 1 3 1 1 9 1
1 2 1 2 5 2 1 2 1 10
可以看到，上半部分和下半部分是对称的，我们考虑一边即可。
若(gcd(i,j)=x)，那么(gcd(ki,kj)=kx)。
因此，显然对于任意(gcd(i,j)=1)，有(gcd(ki,kj)=k)，且充要。我们枚举(k)，对于每个(k)，计算(gcd(ki,kj)=k)的数量即可。
由于(gcd(ki,kj),gcd(kj,ki))被算作分开的两次，而(gcd(i,i))只会被算一次，所以减去1。
因此，对于所有的(i)，计算
[sum_{i=1}^n（sum_{k=1}^{lfloor frac{n}{i}
floor}2*varphi(k)-1)*i
]
预处理(varphi(k))的前缀和即可(O(n))求解。
推导过程
[egin{align}
Ans
&=sum_{i=1}^nsum_{j=1}^ngcd(i,j)\
&=sum_{i=1}^nsum_{j=1}^nsum_{k=1}^{n}[gcd(i,j)==k]\
&=sum_{i=1}^nsum_{j=1}^nsum_{kmid i , j}[gcd(i/k,j/k)==1]\
&=sum_{i=1}^{lfloorfrac{n}{k}
floor}(2sum_{j=1}^{i}sum_{k=1}^n[gcd(i,j)==1]-1)\
&=sum_{i=1}^n（sum_{k=1}^{lfloor frac{n}{i}
floor}2*varphi(k)-1)*i
end{align}
]