一开始没看见F(1) = 0。按一般的约数个数函数推了，后来发现了，一慌：读错题了，但是忽然想到F(1) = 0不过是把gcd == 1的贡献减去了而已。。。写一下推的过程：
设 $ D(x) = \sum_{d|x}^{ } 1 $ 也就是x的约数的个数。（与本题中F的区别就是$ D(1)=1 $)
$ \sum_{i=1}^{n} D(gcd(i, n)) = \sum_{d|n}^{ } \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} D(d) [gcd(k, \frac{n}{d}) == 1] $
$ = \sum_{d|n}^{ } D(d) * \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(k, \frac{n}{d}) == 1] $
$ = \sum_{d|n} D(d) * \phi(\frac{n}{d})$
发现是个狄利克雷卷积的形式，我们先变换一下：(下面这个$ * $表示狄利克雷卷积运算)
$ = D * \phi$ = $ 1 * 1 * \phi$ = $ id * 1$
到这里求解就非常容易了，就是
$ = \sum_{d|n} \frac{n}{d} $
那原题里面不是D函数，而是F，区别在于$ F(1) = 0 $，怎么办
注意到原式子 $\sum_{i=1}^{n} F(gcd(i, n))$ ，我们求出来的是 $ \sum_{i=1}^{n} D(gcd(i, n))$，只有$ gcd(i, n) == 1 $ 的时候，F和D有偏差。
对于每一个$ gcd(i, n) == 1 $ ，我们都刚好多算了$ 1 $，所以最后我们答案多算了$ \phi(n) $，减去即可。
最终
$ Ans = \sum_{d|n} \frac{n}{d} - \phi(n) $
可以在$ O(\sqrt{n})$ 的时间复杂度内求解出来。

回复 @kito :
好吧...... 看到N好大就不敢写根号

回复 @卜卜 :
30000000还是可以承受的吧。而且出题人没造极限数据，达不到$O(\sqrt n)$

根号算法为啥能过啊？？ 这么多零一看就感觉会TLE 感觉只能用Pollard_Rho诶

太轻视了，被运算顺序搞跪了
先是ans*=(x-1)/x，先算(x-1)/x，后相乘
改成ans=ans*(x-1)/x，结果先算ans*(x-1)，一个大数爆unsigned long long了
怒跪

回复 @Pessimist :
这个题好像不需要数组吧

数组开太大会超时，不大不小，1000适合你

VIPEzoi 占领此题 Orz...LPX

为什么一个素数点都没有

EZOI即将占领此题
LPX Orz

Ezoi 即将占领此题 Orz...LPX

哇，读不懂题的我去问大神“因子”什么意思，才知道原来就是“因数”。。

题解上:http://blog.csdn.net/qq_31725915/article/details/52200224

回复 @叶子の宿敌 :
我不加^15,不加','还不是为了给你们复制粘贴着更方便吗？？？？