题面
https://darkbzoj.tk/problem/3512
题解
前置知识
本题不能上手直接反演，这是因为我这么做然后光荣GG了我们发现n不正常地小。
考虑枚举n这一维。设(S(n,m)={sum_{j=1}^{m}}{varphi(nj)})，那么所求即为({sum_{i=1}^{n}}S(i,m))。
预处理出s,r数组，如果(n={prod_{i=1}^{k}}{p_i}^{alpha_i})，那么(s[n]={prod_{i=1}^{k}}p_i)，而(r[n]={frac{n}{s[n]}})。这样，我们就可以从(varphi)函数中提出r，并使得剩下的部分便于操作：（以下r[n]简写成r，s[n]简写成s)
[S(n,m)=r{sumlimits_{j=1}^{m}}{varphi(sj)}
]
[=r{sumlimits_{j=1}^{m}}{varphi(frac{s}{(s,j)}*(s,j)*j)}
]
刚才我们拆n为s和r的另一个好处得到了体现：(frac{s}{(s,j)})和((s,j)、j)都互质。
[原式=r{sumlimits_{j=1}^{m}}{varphi(frac{s}{(s,j)})}varphi((s,j)*j)
]
[=r{sumlimits_{j=1}^{m}}{varphi(frac{s}{(s,j)})}varphi(j)(s,j)
]
[=r{sumlimits_{j=1}^{m}}{varphi(frac{s}{(s,j)})}varphi(j){sumlimits_{d|(s,j)}}{varphi(d)}
]
[=r{sumlimits_{j=1}^{m}}{varphi(j)}{sumlimits_{d|(s,j)}}{varphi(frac{s}{frac{(s,j)}{d}})}
]
[=r{sumlimits_{j=1}^{m}}{varphi(j)}{sumlimits_{d|(s,j)}}varphi({frac{s}{d}})
]
[=r{sumlimits_{d|s}}{varphi(frac{s}{d})}{sumlimits_{j=1}^{m}}[d|j]{varphi(j)}
]
[=r{sumlimits_{d|s}}{varphi(frac{s}{d})}{sumlimits_{j'=1}^{{lfloor}{frac{m}{d}}{
floor}}}{varphi(dj')}
]
[=r{sumlimits_{d|s}}{varphi(frac{s}{d})}S(d,{lfloor}{frac{m}{d}}{
floor})
]
于是可以递归计算了。
递归终止的条件是n=1（用杜教筛求和）或者m=0（返回0）。分析一下复杂度：杜教筛是(O(m^{frac{2}{3}}))；计算函数(S(i,j))时，只要(j<m)，j就一定在({lfloor}{frac{m}{i}}{ floor})的整除集合中。
再加上计算(S(i,j))的时候需要枚举(s[i])的约数，由于(i<10^5)，所以(i)最多有6个不同的质因子，所以(s[i])最多有64个约数。
总时间复杂度为(O(m^{frac{2}{3}}+{sum_{i=1}^{n}}{sqrt{frac{m}{i}}}w(i)))，其中(w(i))指的是(s[i])约数的数量。
视各(w(i))为常数，积分近似可得(O(m^{frac{2}{3}}+overline{w}{sqrt{nm}}))，其中({overline{w}}{leq}64)。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
const ll N = 1e5;
const ll mod = 1e9 + 7;
const ll iv2 = 5e8 + 4;
namespace ModCalc{
inline void Inc(ll &x,ll y){
x += y;if(x >= mod)x -= mod;
}
inline void Dec(ll &x,ll y){
x -= y;if(x < 0)x += mod;
}
inline ll Add(ll x,ll y){
Inc(x,y);return x;
}
inline ll Sub(ll x,ll y){
Dec(x,y);return x;
}
}
using namespace ModCalc;
ll pn;
ll pri[N+5],phi[N+5],sphi[N+5];
bool isp[N+5];
inline void Eular(){
phi[1] = 1;
for(rg ll i = 2;i <= N;i++)isp[i] = 1;
for(rg ll i = 2;i <= N;i++){
if(isp[i])pri[++pn] = i,phi[i] = i - 1;
for(rg ll j = 1;i * pri[j] <= N;j++){
isp[i*pri[j]] = 0;
if(i % pri[j])phi[i*pri[j]] = phi[i] * (pri[j] - 1) % mod;
else{
phi[i*pri[j]] = phi[i] * pri[j] % mod;
break;
}
}
}
for(rg ll i = 1;i <= N;i++)sphi[i] = Add(sphi[i-1],phi[i]);
}
unordered_map<ll,ll>Hash;
inline ll sumphi(ll n){
if(n <= N)return sphi[n];
if(Hash.count(n))return Hash[n];
ll ans = 1ll * (n % mod) * Add(n % mod,1) % mod * iv2 % mod;
ll L,R = 1;
while(R < n){
L = R + 1,R = n / (n / L);
Dec(ans,(R - L + 1) * sumphi(n/L) % mod);
}
return Hash[n] = ans;
}
ll s[N+5],r[N+5];
vector<ll>fac[N+5],g[N+5]; //fac[i]存储i的不同质因子,g[i]存储s[i]的约数
inline void prepro(){
for(rg ll i = 1;i <= pn;i++)
for(rg ll j = pri[i];j <= N;j += pri[i])fac[j].push_back(pri[i]);
for(rg ll i = 1;i <= N;i++){
for(rg ll mask = 0;mask < 1ll << fac[i].size();mask++){
ll cur = 1;
for(rg ll j = 0;j < fac[i].size();j++)
if((bool)(mask&(1ll<<j)))cur *= fac[i][j];
g[i].push_back(cur);
}
s[i] = g[i][g[i].size()-1];
r[i] = i / s[i];
}
}
unordered_map<ll,ll>HashS[N+5];
inline ll S(int n,int m){
if(n == 1)return sumphi(m);
if(!m)return 0;
if(HashS[n].count(m))return HashS[n][m];
ll ans = 0;
for(rg int i = 0;i < g[n].size();i++){
int d = g[n][i];
Inc(ans,phi[s[n]/d] * S(d,m/d) % mod);
}
ans = ans * r[n] % mod;
return HashS[n][m] = ans;
}
int main(){
Eular();
prepro();
ll ans = 0;
ll n,m;
scanf("%lld%lld",&n,&m);
for(rg ll i = 1;i <= n;i++)Inc(ans,S(i,m));
cout << ans << endl;
return 0;
}