（全是套路.jpg）
首先观察这个函数，发现是 (f(n)=prod_j(p_j^{k_j}+1))（设 (n) 质因数分解得到 (prod_jp_j^{k_j})）
然后不知怎么想到的，就等价于 (f(n)=sum_{d|n} [dot frac nd]d)。
终于有了比较靠谱的形式，然后就开始推：
[sum _{i=1}^nf(i)\=sum _{i=1}^nsum_{d|i} [dot frac id]d\=sum _{d=1}^ndsum_{d|i} [dot frac id]\=sum _{d=1}^ndsum_{i=1}^{lfloorfrac nd
floor} [dot i]\=sum _{d=1}^ndsum_{i=1}^{lfloorfrac nd
floor}sum_{t|d,t|i}mu(t)\=sum _{d=1}^ndsum_{t|d}mu(t)lfloorfrac n{dt}
floor\=sum_{T=1}^nlfloorfrac nT
floorsum _{t^2|T}mu(t)frac Tt\=sum_{t=1}^{sqrt n}frac {mu(t)}tsum_{t^2|T}Tlfloorfrac nT
floor\=sum_{t=1}^{sqrt n}frac {mu(t)}tsum_{T=1}^{lfloorfrac n{t^2}
floor}Tt^2lfloorfrac n{Tt^2}
floor\=sum_{t=1}^{sqrt n}mu(t)tsum_{T=1}^{lfloorfrac n{t^2}
floor}Tlfloorfrac{lfloorfrac n{t^2}
floor}{T}
floor\
]
后面那个求和号显然可以除法分块 (O(frac{sqrt n}t)) 求，则
[sum_{t=1}^sqrt n frac{ sqrt n}t=sqrt nsum_{t=1}^sqrt n frac{1}tsim sqrt nln n
]
总复杂度 (O(sqrt nln n))。
然后由于毒瘤出题人把 (n) 出到了 (10^{13})，你发现你被卡常数了 爆筋
- 瓶颈在除法分块，把这个除法分块写成比较快的版本，可以快至少一倍；
- 注意到 (g(n)=sum_{T=1}^nTlfloorfrac n{T} floor=sum_{i=1}^nsigma(i)) ，这玩意可以线筛。于是把较小的 (g) 拿去线筛预处理一下，省下的计算也比较可观。
至此大概就可以过了。
#include<cstdio>
typedef long long ll;
const int D=3.2e6;
int M,p[D],np[D],k,mu[D],t0[D],t1[D],s,sig[D];ll n;
inline int G(ll n){
if(n<D)return sig[n];
int res=0;ll d,e,i;
e=n%M;
for(i=1;i*i<=n;i++){
d=e,e=n/(i+1)%M;
res=(res+i*d*2)%M;
if(n>=i*(i+1))res=(res+(d-e)*(d+e+1)%M*i)%M;
}
return res;
}
int main(){
scanf("%lld%d",&n,&M);
mu[1]=1,sig[1]=1;
for(int i=2;i<D;i++){
if(!np[i])p[++k]=i,mu[i]=-1,t0[i]=t1[i]=1;
if(t1[i]==1)sig[i]=sig[t0[i]]+i;
else sig[i]=sig[t1[i]]*sig[i/t1[i]];
for(int j=1;j<=k&&i*p[j]<D;j++){
np[i*p[j]]=1;
t0[i*p[j]]=i;
if(i%p[j]){
mu[i*p[j]]=-mu[i];
t1[i*p[j]]=i;
}
else{
t1[i*p[j]]=t1[i];
break;
}
}
}
for(int i=1;i<D;i++)sig[i]=(sig[i]*2+sig[i-1])%M;
for(ll i=1;i*i<=n;i++)if(mu[i])
s=(s+G(n/(i*i))*mu[i]*i)%M;
if(s<0)s+=M;
if(s&1)s+=M;
printf("%d
",s>>1);
return 0;
}