【51nod】1239 欧拉函数之和

【题意】给定n，求Σφ(i)，n<=10^10。

【算法】杜教筛

【题解】

$\sum_{i=1}^{n}(\varphi *I)(i)=\sum_{i=1}^{n}\sum_{d|i}\varphi(d)=\sum_{i=1}^{n}\sum_{d=1}^{\frac{n}{i}}\varphi(d)=\frac{i(i+1)}{2}$