莫比乌斯反演学习笔记

学习笔记 数论

感觉这个东西很需要感觉，要多练习。。。

目录

• 莫比乌斯反演学习笔记
  • 基础知识
    • 莫比乌斯函数
    • 公式与证明
  • 练习
    • [HAOI 2011] Problem b
      • 思路
      • 代码
    • [BZOJ 2818] Gcd
      • 思路
      • 代码
    • [SDOI 2014] 数表
      • 思路
      • 代码
    • [BZOJ 2154] Crash的数字表格
      • 思路
      • 代码
    • [SDOI 2015] 约数个数和
      • 思路
      • 代码

基础知识

莫比乌斯函数

定义整数域上的数论函数：

$$\mu(n)= \begin{cases} 1 &\quad& n=1\\ (-1)^k &\quad& n=\prod_{i=1}^k p_i\\ 0 &\quad& \exists p^2 \mid n \end{cases}$$
这个函数就是莫比乌斯函数。

1. 性质

   • 显然，$\mu(n)$为积性函数，但不是完全积性的，不过我们依然可以用欧拉筛法$O(n)$求出；
   • $\sum_{d \mid n}\mu(d)=[n=1]$，所以$\mu(n)$的狄利克雷前缀和就是元函数$e(n)$。将$\mu(n)$看作容斥系数的话就很好理解了；
   • $\sum_{d \mid n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}$，设$F(n)=n,f(n)=\varphi(n)$反演一下就出来了，学完下面的就能证了。

2. 练习：[BZOJ 2440] 完全平方数

   • 其实是用到$\mu(n)$作为容斥系数的应用，这个和后面的反演有些类似；
   • 考虑二分答案，则我们只需快速计算$1$~$mid$内无平方因子的数的个数即可；
   • 显然算出有平方因子的数的个数更好算，用容斥原理则可知：
     $$sum=\sum_{i=1}^x \lfloor\frac{mid}{p_i^2}\rfloor-\sum_{i=1}^{x-1}\sum_{j=i+1}^x \lfloor\frac{mid}{p_i^2p_j^2}\rfloor+\cdots$$
   • 观察发现，枚举的这个$p_ip_j\cdots$前面的系数刚好和$\mu(p_ip_j\cdots)$值一样，那么$sum=\sum_{i=1}^{\lfloor\sqrt{mid}\rfloor}\mu(i)\times\lfloor\frac{mid}{i^2}\rfloor$，因为如果$i$中有重复质因子，$\mu(i)=0$刚好不影响，反正就很神奇；
   • 复杂度为$O(n+\sqrt{n}\log n)$。

   代码：

#include <cstdio>
#include <cmath>
using std::sqrt;
using std::floor;
const int INF=2e9,MAXN=50005;
int miu[MAXN];
long long sqr[MAXN];
inline void Euler_miu(){
    static int prm[MAXN];
    static bool notP[MAXN];
    notP[1]=true,miu[1]=1;
    for(int i=2;i<MAXN;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            miu[i]=-1;
        }
        for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
            tmp=i*prm[j];
            notP[tmp]=true;
            if(i%prm[j]==0){
                miu[tmp]=0;
                break;
            }
            else miu[tmp]=-miu[i];
        }
    }
}
inline void pre_tab(){
    for(int i=1;i<MAXN;++i)
        sqr[i]=(long long)i*i;
}
inline int cal(int r){
    long long ret=0;
    for(int i=1,lim=floor(sqrt(r));i<=lim;++i)
        ret+=r/sqr[i]*miu[i];
    return ret;
}
inline int bin_chop(int k){
    int l=1,r=INF;
    long long mid;
    while(l<=r){
        mid=(long long)l+r>>1;
        if(cal(mid)>=k) r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main(){
    Euler_miu();
    pre_tab();
    int T;
    scanf("%d",&T);
    int k;
    while(T--){
        scanf("%d",&k);
        printf("%d\n",bin_chop(k));
    }
    return 0;
}

公式与证明

对于两个函数$F(n),f(n)$，若$F(n)$是$f(n)$的狄利克雷前缀和，即：$F(n)=\sum_{d \mid n} f(d)$，则有如下结论：

$$\begin{eqnarray*} f(n) &=& \sum_{d \mid n}\mu(d)\times F(\frac{n}{d}) \tag{1}\\ &=& \sum_{n \mid d}\mu(\frac{d}{n})\times F(d) \tag{2} \end{eqnarray*}$$

1. 形式一：

   • 这个也就是说$\mu(n)$与$F(n)$的狄利克雷卷积$(\mu\ast F)(n)=f(n)$；
   • 证明：
     $$\begin{eqnarray*} 右边 &=& \sum_{d \mid n}\mu(d)\sum_{k \mid\frac{n}{d}} f(k)\\\ &=& \sum_{k \mid n}f(k)\sum_{d \mid\frac{n}{k}}\mu(d)\\ &=& \sum_{k \mid n}f(k)\cdot[d=\frac{n}{k}=1]\\ &=& f(n)\\ &=& 左边 \end{eqnarray*}$$

2. 形式二：

   • 这个形式有些“奇怪”，但却是最常用的一种；
   • 证明（令$k=\frac{d}{n}$）：
     $$\begin{eqnarray*} 左边 &=& \sum_{k=1}^{+\infty}\mu(k)\times F(kn)\\ &=& \sum_{k=1}^{+\infty}\mu(k)\sum_{d \mid kn} f(d)\\ &=& \sum_{n \mid d}f(d)\sum_{k \mid\frac{d}{n}}\mu(k)\\ &=& \sum_{n \mid d}f(d)\cdot[d=\frac{d}{n}=1]\\ &=& f(n)\\ &=& 右边 \end{eqnarray*}$$

3. 应用方法

   • 即使知道了公式，我们发现这玩意似乎并无卵用，其实不然；
   • 如果我们要求$f(n)$，但是不容易迅速得出，可以考虑设$F(n)=\sum_{d \mid n}f(d)$，若$F(n)$很好求，那么反演一下就出来了；
   • 其实这个反演过程就是一种容斥，加加减减就神奇的算出来了；
   • 在应用过程中$F(n)$通常是$\lfloor\frac{a}{b}\rfloor$的形式，为了迅速反演求出$f(n)$，常常利用数论分段求和的技巧；
   • 以上这些见到下面的题就清楚了，这个东西多练才能有感觉。

练习

[HAOI 2011] Problem b

思路

• 设$f_z(x,y)=\sum_{i=1}^x \sum_{j=1}^y [\gcd(i,j)=z]$；
• 则$ans=f_k(b,d)-f_k(a-1,d)-f_k(b,c-1)+f_k(a-1,c-1)$；
• 先在考虑怎么快速的求$f_z(x,y)$；
• 设$F_z(x,y)=\sum_{i=1}^x \sum_{j=1}^y [z \mid\gcd(i,j)]$，则显然$F_z(x,y)=\lfloor\frac{x}{z}\rfloor\times\lfloor\frac{y}{z}\rfloor$；
• 又易知$F_z(x,y)=\sum_{z \mid d} f_d(x,y)$，有一步不是很显然的变形：$f_z(x,y)=\sum_{z \mid d}\mu(\frac{d}{z})\times F_d(x,y)$，这个其实也不是反演，还是容斥，类似上一题的原理，请自行思考。

代码

#include <cstdio>
#include <algorithm>
using std::min;
const int MAXN=50005;
int miu[MAXN],sum[MAXN];
inline void Euler_miu(){
    static int prm[MAXN];
    static bool notP[MAXN];
    notP[1]=true,miu[1]=1;
    for(int i=2;i<MAXN;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            miu[i]=-1;
        }
        for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
            tmp=i*prm[j];
            notP[tmp]=true;
            if(i%prm[j]==0){
                miu[tmp]=0;
                break;
            }
            else miu[tmp]=-miu[i];
        }
    }
}
inline void pre_sum(){
    Euler_miu();
    for(int i=1;i<MAXN;++i)
        sum[i]=sum[i-1]+miu[i];
}
inline int cal(int n,int m){
    int ret=0;
    for(int i=1,lim=min(n,m),r;i<=lim;i=r+1){
        r=min(n/(n/i),m/(m/i));
        if(r>lim) r=lim;
        ret+=(sum[r]-sum[i-1])*(n/i)*(m/i);
    }
    return ret;
}
inline int solve(int a,int b,int c,int d,int k){
    --a,--c;
    a/=k,b/=k,c/=k,d/=k;
    return cal(b,d)-cal(b,c)-cal(a,d)+cal(a,c);
}
int main(){
    pre_sum();
    int n;
    scanf("%d",&n);
    int a,b,c,d,k;
    while(n--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("%d\n",solve(a,b,c,d,k));
    }
    return 0;
}

[BZOJ 2818] Gcd

思路

• 类似上一题，不过如果我们枚举质数进行上一题的操作显然会T，考虑怎么优化；
• 若按上一题的操作，则$ans=\sum_{p}^{\min(n,m)}\sum_{d=1}^{\min(n,m)}\mu(d)\times\lfloor\frac{n}{pd}\rfloor\times\lfloor\frac{m}{pd}\rfloor$；
• 令$t=pd$，则$ans=\sum_{t=1}^{\min(n,m)}\lfloor\frac{n}{t}\rfloor\times\lfloor\frac{m}{t}\rfloor\sum_{p \mid t}\mu(\frac{t}{p})$；
• 现在，瓶颈在于求$\sum_{p \mid t}\mu(\frac{t}{p})$的前缀和，考虑暴力枚举质数，则根据素数定理有$O(\frac{n}{\log n})$个，用每个质数更新在$1$~$\min(n,m)$内的倍数则有$O(\log n)$个，所以求前缀和的复杂度就成了$O(n)$了。

代码

#include <cstdio>
const int MAXN=1e7+5;
int prm[MAXN],miu[MAXN];
inline void Euler_miu(int n){
    static bool notP[MAXN];
    notP[1]=true,miu[1]=1;
    for(int i=2;i<=n;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            miu[i]=-1;
        }
        for(int j=1,tmp;j<=prm[0] && i*prm[j]<=n;++j){
            tmp=i*prm[j];
            notP[tmp]=true;
            if(i%prm[j]==0){
                miu[tmp]=0;
                break;
            }
            else miu[tmp]=-miu[i];
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    Euler_miu(n);
    long long ans=0;
    for(int i=1;i<=prm[0];++i){
        for(int j=prm[i],k=1,tmp;j<=n;j+=prm[i],++k){
            tmp=n/j;
            ans+=(long long)miu[k]*tmp*tmp;
        }
    }
    printf("%lld",ans);
    return 0;
}

[SDOI 2014] 数表

思路

• 限制$a$十分烦人，先考虑没有限制的情况；
• 设$f(x)=\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=x]$，则由之前的经验，可以很容易得到$f(x)=\sum_{x \mid d}\mu(\frac{d}{x})\times\lfloor\frac{n}{d}\rfloor\times\lfloor\frac{m}{d}\rfloor$；
• 约数和函数$\sigma(n)$可以线性筛出来，则$ans=\sum_{i=1}^{\min(n,m)}\sigma(i)\times f(i)$；
• 把$f(i)$展开，则：
  $$\begin{eqnarray*} ans &=& \sum_{i=1}^{\min(n,m)}\sigma(i)\times\left(\sum_{i \mid d}\mu(\frac{d}{i})\times\lfloor\frac{n}{d}\rfloor\times\lfloor\frac{m}{d}\rfloor\right)\\ &=& \sum_{d=1}^{\min(n,m)}\lfloor\frac{n}{d}\rfloor\times\lfloor\frac{m}{d}\rfloor\times\left(\sum_{i \mid d}\sigma(i)\times\mu(\frac{d}{i})\right) \end{eqnarray*}$$
• 这样只要求出$\sum_{i \mid d}\sigma(i)\times\mu(\frac{d}{i})$的前缀和就能$O(\sqrt{n})$回答没有$a$限制的询问了，和上一题一样，也是枚举$i$，更新其倍数，复杂度$O(n \log n)$；
• 现在考虑怎么处理$a$的限制；
• 可以采用离线，将询问按$a$升序排序、$\sigma(i)\times\mu(\frac{d}{i})$按$\sigma(i)$升序排序，用树状数组维护前缀和，每次将符合限制的$\sigma(i)\times\mu(\frac{d}{i})$加入即可；
• 总复杂度为$O(n \log^2 n+q \sqrt{n}\log n)$。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using std::min;
using std::sort;
const int MAXQ=2e4+5,MAXN=1e5+5;
int miu[MAXN];
struct data{
    int id;
    long long c;
    friend bool operator< (const data &a,const data &b){
        return a.c<b.c;
    }
}sgm[MAXN];
struct query{
    int id,n,m,a,ans;
    static bool cmp_a(const query &a,const query &b){
        return a.a<b.a;
    }
    static bool cmp_id(const query &a,const query &b){
        return a.id<b.id;
    }
}qry[MAXQ];
class BIT{
    private:
        unsigned c[MAXN];
        int lowbit(int x){return x&-x;}
        unsigned qry(int r){
            unsigned ret=0;
            for(;r;r-=lowbit(r))
                ret+=c[r];
            return ret;
        }
    public:
        void add(int l,unsigned x){
            for(;l<MAXN;l+=lowbit(l))
                c[l]+=x;
        }
        unsigned qry(int l,int r){
            return qry(r)-qry(l-1);
        }
}ta;
inline void Euler_sv(){
    static int prm[MAXN];
    static long long dProd[MAXN],prodS[MAXN];
    static bool notP[MAXN];
    notP[1]=true,miu[1]=sgm[1].c=1;
    for(int i=2;i<MAXN;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            dProd[i]=i,prodS[i]=1+i;
            miu[i]=-1,sgm[i].c=1+i;
        }
        for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
            tmp=i*prm[j];
            notP[tmp]=true;
            if(i%prm[j]==0){
                dProd[tmp]=dProd[i]*prm[j];
                prodS[tmp]=prodS[i]+dProd[tmp];
                miu[tmp]=0,sgm[tmp].c=sgm[i].c/prodS[i]*prodS[tmp];
                break;
            }
            else{
                dProd[tmp]=prm[j];
                prodS[tmp]=1+prm[j];
                miu[tmp]=-miu[i],sgm[tmp].c=sgm[i].c*sgm[prm[j]].c;
            }
        }
    }
}
inline unsigned cal(int n,int m){
    unsigned ret=0;
    for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
        r=min(n/(n/l),m/(m/l));
        if(r>lim) r=lim;
        ret+=(unsigned)(n/l)*(m/l)*ta.qry(l,r);
    }
    return ret;
}
int main(){
    Euler_sv();
    for(int i=1;i<MAXN;++i)
        sgm[i].id=i;
    sort(sgm+1,sgm+MAXN);
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d%d%d",&qry[i].n,&qry[i].m,&qry[i].a);
        qry[i].id=i;
    }
    sort(qry+1,qry+q+1,query::cmp_a);
    for(int i=1,j,k=1;i<=q;++i){
        for(;sgm[k].c<=qry[i].a;++k){
            for(j=1;j*sgm[k].id<MAXN;++j)
                ta.add(j*sgm[k].id,(unsigned)miu[j]*sgm[k].c);
        }
        qry[i].ans=cal(qry[i].n,qry[i].m)&INT_MAX;
    }
    sort(qry+1,qry+q+1,query::cmp_id);
    for(int i=1;i<=q;++i)
        printf("%d\n",qry[i].ans);
    return 0;
}

[BZOJ 2154] Crash的数字表格

思路

• 显然要把$\text{lcm}(x,y)$化为$\gcd(x,y)$，所以$ans=\sum_{i=1}^n \sum_{j=1}^m \frac{i \times j}{\gcd(i,j)}$；
• 枚举$\gcd(x,y)$，则：
  $$\begin{eqnarray*} ans &=& \sum_{i=1}^n \sum_{j=1}^m \sum_{d=1}^{\min(n,m)}\frac{i \times j}{d}\cdot[\gcd(i,j)=d]\\ &=& \sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\frac{i \times j \times d^2}{d}\cdot[\gcd(i,j)=1]\\ &=& \sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} d \times i \times j \cdot[\gcd(i,j)=1] \end{eqnarray*}$$
• 设$f(x,y)=\sum_{i=1}^x \sum_{j=1}^y i \times j \cdot[\gcd(i,j)=1]$；
• 则$ans=\sum_{d=1}^{\min(n,m)} d \times f(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$；
• 考虑$f(x,y)$有个$\gcd(i,j)$的限制，所以考虑反演，设$g(x,y)=\sum_{i=1}^x \sum_{j=1}^y i \times j=\frac{x(x+1)}{2}\times\frac{y(y+1)}{2}$；
• 则$f(x,y)=\sum_{i=1}^{\min(x,y)} i^2 \times\mu(i)\times g(\lfloor\frac{x}{i}\rfloor,\lfloor\frac{y}{i}\rfloor)$；
• 所以可以$O(\sqrt{n})$计算$f(x,y)$，再$O(\sqrt{n})$计算$ans$，总复杂度是$O(n)$。

代码

#include <cstdio>
#include <algorithm>
using std::min;
const int MAXN=1e7+5,P=20101009;
int inv_6;
int miu[MAXN],tab[MAXN];
inline void Euler_miu(){
    static int prm[MAXN];
    static bool notP[MAXN];
    notP[1]=true,miu[1]=1;
    for(int i=2;i<MAXN;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            miu[i]=-1;
        }
        for(int j=1,tmp;tmp=i*prm[j],j<=prm[0] && tmp<MAXN;++j){
            notP[tmp]=true;
            if(i%prm[j]==0){
                miu[tmp]=0;
                break;
            }
            else miu[tmp]=-miu[i];
        }
    }
}
inline void pre_tab(){
    Euler_miu();
    for(int i=1;i<MAXN;++i)
        tab[i]=(tab[i-1]+(long long)i*i*miu[i]%P+P)%P;
    for(int i=2;i<MAXN;++i)
        miu[i]+=miu[i-1];
}
inline int sum(int n,int m){
    return (long long)((long long)n*(n+1)>>1)%P*(((long long)m*(m+1)>>1)%P)%P;
}
inline int cal(int n,int m){
    int ret=0;
    for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
        r=min(n/(n/l),m/(m/l));
        if(r>lim) r=lim;
        ret=(ret+(long long)(tab[r]-tab[l-1]+P)%P*sum(n/l,m/l)%P)%P;
    }
    return ret;
}
int main(){
    pre_tab();
    int n,m;
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
        r=min(n/(n/l),m/(m/l));
        if(r>lim) r=lim;
        ans=(ans+(long long)cal(n/l,m/l)*(((long long)(l+r)*(r-l+1)>>1)%P)%P)%P;
    }
    printf("%d",(ans+P)%P);
    return 0;
}

[SDOI 2015] 约数个数和

思路

• 结论神题。。。
• 首先需要知道$\tau(xy)=\sum_{i \mid x}\sum_{j \mid y}[\gcd(i,j)=1]$；
• 证明：
  
  1. 左边，对于$xy$的任意一个质因子$p$，设$a,b$是满足$p^a \mid x,p^b \mid y$的最大值；
  2. 那么，$p$对于$\tau(xy)$的贡献是$a+b+1$；
  3. 而右边，对于$i$有$a$种可能被$p$整除（被$p^1$~$p^a$整除），$j$同理有$b$种，那么$i,j$中任意一个质因子不含$p$的有$a+b$种，加上都不含的情况则为$a+b+1$种；
  4. 考虑到$\tau(n)$是积性函数且不同质因子间对互质关系不影响，所以左边$=\prod_{i=1}^k (a_i+b_i+1)=$右边；
• 知道这个结论后就可以变形了：
  $$\begin{eqnarray*} ans &=& \sum_{i=1}^n \sum_{j=1}^m \sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1]\\ &=& \sum_{i=1}^n \sum_{j=1}^m \lfloor\frac{n}{i}\rfloor\times\lfloor\frac{m}{i}\rfloor\cdot[\gcd(i,j)=1] \end{eqnarray*}$$
• 反演一下：
  $$\begin{eqnarray*} ans &=& \sum_{i=1}^n \sum_{j=1}^m \lfloor\frac{n}{i}\rfloor\times\lfloor\frac{m}{i}\rfloor\sum_{d \mid\gcd(i,j)}\mu(d)\\ &=& \sum_{d=1}^{\min(n,m)}\mu(d)\left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{id}\rfloor\times\lfloor\frac{m}{jd}\rfloor\right)\\ &=& \sum_{d=1}^{\min(n,m)}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{id}\rfloor\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{jd}\rfloor \end{eqnarray*}$$
• 令$f(n)=\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$；
• 则$ans=\sum_{d=1}^{\min(n,m)}\mu(d)\times f(\lfloor\frac{n}{d}\rfloor)\times f(\lfloor\frac{m}{d}\rfloor)$；
• “很容易”发现$f(n)=sum_{i=1}^n \tau(i)$，线性筛就可以求出来了；
• 那么单次询问的复杂度就变成$O(\sqrt{n})$了，操作和之前的都一样；

代码

#include <cstdio>
#include <algorithm>
using std::min;
const int MAXN=50005;
int miu[MAXN];
long long tao[MAXN];
inline void Euler_sv(){
    static int prm[MAXN],dExp[MAXN];
    static bool notP[MAXN];
    notP[1]=true,dExp[1]=miu[1]=tao[1]=1;
    for(int i=2;i<MAXN;++i){
        if(!notP[i]){
            prm[++prm[0]]=i;
            dExp[i]=1;
            miu[i]=-1,tao[i]=2;
        }
        for(int j=1,tmp;j<=prm[0] && i*prm[j]<MAXN;++j){
            tmp=i*prm[j];
            notP[tmp]=true;
            if(i%prm[j]==0){
                dExp[tmp]=dExp[i]+1;
                miu[tmp]=0;
                tao[tmp]=tao[i]/(dExp[i]+1)*(dExp[tmp]+1);
                break;
            }
            else{
                dExp[tmp]=1;
                miu[tmp]=-miu[i];
                tao[tmp]=tao[i]*tao[prm[j]];
            }
        }
    }
}
inline void pre_tab(){
    Euler_sv();
    for(int i=2;i<MAXN;++i){
        miu[i]+=miu[i-1];
        tao[i]+=tao[i-1];
    }
}
inline long long cal(int n,int m){
    long long ret=0;
    for(int l=1,r,lim=min(n,m);l<=lim;l=r+1){
        r=min(n/(n/l),m/(m/l));
        if(r>lim) r=lim;
        ret+=(long long)tao[n/l]*tao[m/l]*(miu[r]-miu[l-1]);
    }
    return ret;
}
int main(){
    pre_tab();
    int T;
    scanf("%d",&T);
    int n,m;
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%lld\n",cal(n,m));
    }
    return 0;
}