[洛谷P5106]dkw的lcm：欧拉函数+容斥原理+扩展欧拉定理
分析
考虑使用欧拉函数的计算公式化简原式，因为有：
[lcm(i_1,i_2,...,i_k)=p_1^{q_{1 max}} imes p_2^{q_{2 max}} imes ... imes p_m^{q_{m max}}
]
其实就是分解质因数，丢到那个式子里：
[varphi(lcm(i_1,i_2,...,i_k))=prod (p_i-1)p_i^{q_{i max}-1}
]
容易发现可以分开讨论每个质数，计算每个(p_i^j)在多少种(i_1 sim i_k)的取值方案中作为某一项的倍数出现，这里可以容斥做，然后把产生的贡献乘到答案里即可。质数取模的话，不是有扩展欧拉定理嘛，模个(1e9+6)就好了。
时间复杂度？不知道，大概在(O(n) sim O(nlogn))之间吧。
代码
int main(){
n=read(),k=read();
pre_process();//这个是筛质数
int tot=qpow(n,k,MOD-1);
rin(i,1,cnt){
int p=prm[i],temp=n/p;
ans=1ll*ans*qpow(p-1,(tot-qpow(n-temp,k,MOD-1)+MOD-1)%(MOD-1),MOD)%MOD;
while(1){
temp/=p;if(!temp) break;
ans=1ll*ans*qpow(p,(tot-qpow(n-temp,k,MOD-1)+MOD-1)%(MOD-1),MOD)%MOD;
}
}
printf("%d
",ans);
return 0;
}