思路：

直接上点分治+容斥计算每个因数对应的贡献即可。

代码：

#include
    
     #define ri register intusing namespace std;const int rlen=1<<18|1;inline char gc(){
    	static char buf[rlen],*ib,*ob;	(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));	return ib==ob?-1:*ib++;}inline int read(){
    	int ans=0;	char ch=gc();	while(!isdigit(ch))ch=gc();	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();	return ans;}typedef long long ll;const int N=1e5+5;vector
     
      e[N],fac[N],coe[N];int n,a[N],lim=0,all,mx,siz[N],rt,Tim[N],cnt[N],mul[N],tim=0;bool vis[N],chk[N];ll ans=0;inline int get(int x){
    	if(mul[x])return mul[x];	if(x<2)return mul[x]=x;	int ret=1;	for(ri i=0;i