题意：提前给出\(k\)，求\(\sum\limits_{i=1}^n \sum\limits_{j=1}^m gcd(i,j)^k\)

---

套路推♂倒

\[ \sum_{D=1}^n \sum_{d|D} d^k\mu(\frac{D}{d}) \frac{n}{D} \frac{m}{D} \]

是一个\(g = idk * \mu\)啊，单位幂函数和莫比乌斯函数的卷积！

\(g(1) = 1\)

\(g(p) = -1 + p^k\)

因为带着\(\mu\)，只有sf才有贡献

所以\(p \mid i\)只能把\(p\)放到\(d^k\)里了，就是\(g(i)\cdot p\)

或者考虑\(g(p^k)\)只有1和p有贡献也可以，直接得到计算公式再递推

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=5e6+5, INF=1e9, P=1e9+7;#define pii pair
         
          #define MP make_pair #define fir first#define sec secondtypedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;} int n, m, k;int notp[N], p[N], mu[N];ll pk[N], g[N];inline ll Pow(ll a, int b) { ll ans = 1; for(; b; b>>=1, a=a*a%P) if(b&1) ans = ans*a%P; return ans;}inline ll powk(int a) {return pk[a] ? pk[a] : pk[a]=Pow(a, k);}void sieve(int n) { mu[1] = 1; g[1] = 1; for(int i=2; i<=n; i++) { if(!notp[i]) p[++p[0]] = i, mu[i] = -1, g[i] = -1 + powk(i); for(int j=1; j<=p[0] && i*p[j]<=n; j++) { int t = i*p[j]; notp[t] = 1; if(i%p[j] == 0) { g[t] = g[i]*powk(p[j])%P; mu[t] = 0; break; } g[t] = g[i]*g[p[j]]%P; mu[t] = -mu[i]; } } for(int i=1; i<=n; i++) g[i] = (g[i] + g[i-1])%P;}ll cal(int n, int m) { ll ans=0; int r; for(int i=1; i<=n; i=r+1) { r = min(n/(n/i), m/(m/i)); ans = (ans+ (g[r] - g[i-1]) * (n/i)%P * (m/i)%P )%P; } return (ans + P) %P;}int main() { //freopen("in","r",stdin); int T=read(); k=read(); sieve(N-1); while(T--) { n=read(); m=read(); if(n>m) swap(n, m); printf("%lld\n", cal(n, m)); }}