【BZOJ 2705】[SDOI2012] Longge的问题

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2705
离线版题目：http://paste.ubuntu.com/20283268/

这题真的是蜜汁复杂度。
自己想的时候想到了，然而没敢写QAQ

首先是枚举gcd，然后搞phi或者mu
这个很显然，但只能过60%的数据

因为这个题是求gcd（i，n），所以gcd的取值只会有σ（n）个（有一个是定值），也就是n的因数的个数
然后用sqrt(n)来求每个因数的phi()

这样的话，时间复杂度上界是（sqrt(n)）^2=O(n)的
这题n=10^9那不T到死QAQ
然而万能的vfk告诉我们，10^9内σ（n）最大为1000的样子，这样就不会T了QAQ
前排膜拜vfk：http://vfleaking.blog.163.com/blog/static/174807634201341913040467/
前排膜拜hht：http://techotaku.lofter.com/post/4856f0_634219b
ps:hht告诉我们，除数函数可以线筛，然而一脸懵逼QAQ

然而这题的还有一个trick，求phi（）那里，还可以dfs算QAQ
复杂度更优！快4倍的样子
DFS-version：https://oi.abcdabcd987.com/eight-gcd-problems/（我就偷懒不写啦！）
original-version:

#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;

inline LL Get_Phi(LL n){
	LL ret = n;
	for (int i=2,lim=ceil(sqrt(n));i<=lim;i++) if (n % i == 0) {
		ret = ret*(i-1)/i;
		while (n % i == 0) n /= i;
	}
	if (n > 1) ret = ret*(n-1)/n;
	return ret;
}

int main(){
	LL n,vout=0; scanf("%lld",&n);
	for (int i=1,lim=ceil(sqrt(n));i<=lim;i++) if (n%i == 0) {
		vout += (LL)i*Get_Phi(n/i);
		if (i*i < n) vout += (LL)(n/i)*Get_Phi(i);
	}
	printf("%lld\n",vout);
	return 0;
} 

—————————— UPD 2017.4.8 ——————————
找到这题的爸爸了：BZOJ 4802
也是求$\phi (n)$但$n \le 10^{18}$