pe-0516

5-光滑数是指最大质因数不超过5的数.你要在1e12范围内对于欧拉函数是光滑数的所有数字求和.

发现满足条件的数字一定有以下性质:

$$2^a3^b5^cp_1p_2...$$

其中abc随便取,后面的p数组都满足 $p-1=2^x3^y5^z$ .
于是暴搜所有前半部分和质数部分,拼一起求和.

但是实际上比较考验剪枝能力.
常规枚举每个质数选和不选会T飞.
对于一个质数,我们枚举和这个质数下一个相乘的质数,然后递归下去,同时排序之后一旦大于立刻剪枝,这样的质数选择是单调且不重的,而且才能真正快速的算出来答案,见代码:

u32 res;
void dfs2(int num,i64 prod){
	for(int i=1;i<=top;++i){
		if(tmp[i]*prod>lim)break;
		else{
			res+=tmp[i]*prod;
		}
	}
	for(int i=num;i<=ttop;++i){
		if(prod*pp[i]<=lim)
			dfs2(i+1,prod*pp[i]);
		else break;
	}
}