/* 常见数论函数 e(n)=[n=1] 1(n)=1 id(n)=n d(n)=sum{1} (1<=i<=n&&i|n) SIG(n)=sum{i} (1<=i<=n&&i|n) 常见关系 e=u*1 d=1*1 SIG=id*1 id=phi*1 杜教筛 g(1->i->n)*f(1->n/i) = (g*f)(1->n) g(1)*f(1->n) = (g*f)(1->n) - g(2->i->n)*f(1->n/i) phi*I = id I(1)*phi(1->n) = (I*phi)(1->n) - I(2->i->n)*phi(1->n/i) phi(1->n) = id(1->n) - phi(1->n/i) phi(1->n) = n*(n+1)/2 - phi(1->n/i), (2<=i<=n)g */ //杜教筛求 phi(n) 前缀和 ll sum_phi(ll n){// 2e9 is ok static map<ll,ll> mp; if(n<maxn) return PHI[n]; ll ret=mp[n]; if(ret!=0) return ret; ret=n*(n+1)/2; for(ll i=2,ed;i<=n;i=ed+1){ ed=n/(n/i); ret-=(ed-i+1)*sum_phi(n/i); } if(n>maxn) mp[n]=ret; return ret; }