HDU-6868 多校(莫比乌斯反演)

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e7+6;
const int mod=1e9+7;
const int inv2=mod+1>>1;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
const int _inv=mod-(mod+1>>1);
int g[N],f[N],pri[N],sum[N];
bool vis[N];
int cnt=0;
void pre(){
    g[1]=1;f[1]=0;
    for(int i=2;i<N;i++){
        if(!vis[i]){
            pri[++cnt]=i;
            g[i]=_inv;
            f[i]=1;
        }
        for(int j=1;j<=cnt&&i*pri[j]<N;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                f[i*pri[j]]=f[i];
                g[i*pri[j]]=0;
                break;
            }
            f[i*pri[j]]=f[i]+1;
            g[i*pri[j]]=1LL*g[i]*_inv%mod;
        }
    }
    for(int i=1;i<N;i++){
        f[i]=1<<f[i];
        sum[i]=(1LL*sum[i-1]+f[i])%mod;
    }
}
ll F(int m,int n){
    if(m==0)return 0;
    if(m==1)return f[n];
    if(n==1)return sum[m];
    ll ans=0;
    for(int d=1;d*d<=n;d++){
        if(n%d==0){
            if(g[d]){
                ans+=F(m/d,d)*g[d]%mod;
            }
            if(d*d!=n&&g[n/d]){
                int x=n/d;
                ans+=F(m/x,x)*g[x]%mod;
            }
            if(ans>=mod)ans%=mod;
        }
    }
    ans=ans*f[n]%mod;
    return ans;
}
int main(){
    pre();
    int t;cin>>t;
    while (t--)
    {
        int n,m;
        sc("%d%d",&n,&m);
        pr("%lld\n",F(m,n));
    }
}