任务

答案mod 1e9+7.

解法

容易写出反演：

Ans=∑T=1nTk∗∑i=1⌊nT⌋⌊niT⌋⌊miT⌋μ(i)

∑⌊nT⌋i=1⌊niT⌋⌊miT⌋μ(i)这个因式显然是经典的

分块处理；

同时我们还发现，当

T满足

⌊nT⌋和

⌊mT⌋相等时，这个因式是相等的。

所以我们还可以对

T进行

分块。

总的时间复杂度就是

O(n)。

---

另外的Trick：

当我们在对T进行分块之前，

我们还需预处理出Tk的前缀和。

由于逐个预处理Tk会超时，所以可以考虑利用线性筛法预处理Tk。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const char* fin="ex4161.in";const char* fout="ex4161.out";const ll inf=0x7fffffff;const ll maxn=5000007,mo=1e9+7;ll n,m,N,i,j,k,ans,t;ll mu[maxn],p[maxn],s[maxn];bool bz[maxn];ll qpower(ll a,ll b){    ll c=1;    while (b){        if (b&1) c=c*a%mo;        a=a*a%mo;        b>>=1;    }    return c;}int main(){    scanf("%d%d%d",&n,&m,&N);    if (n>m) swap(n,m);    mu[1]=1;    s[1]=1;    for (i=2;i
          
           =maxn) break; bz[k]=true; s[k]=s[i]*s[p[j]]%mo; if (i%p[j]==0){ mu[k]=0; break; }else mu[k]=-mu[i]; } } for (i=1;i
          
         
        
       
      
     

Warning

注意卡常，先预算出⌊nT⌋和⌊mT⌋，可大幅降低常数。