3881专题

【ZOJ】3881 From the ABC conjecture【暴力容斥】

传送门:【ZOJ】3881 From the ABC conjecture 复杂度大概 O(N0.67) O(N^{0.67}),我也不会算www,首先转换一下(我们是根据积性函数打表找规律得到的,也可以推出来)使得: g(N)=∏pi ϵ N(pia+1) g(N)=\prod_{pi~\epsilon ~N} (pi^a+1) 暴力展开发现贡献为: h(N)=