Sum of gcd of Tuples【容斥定理】

题意：

  考虑长度为 (N) 且由 (1) 到 (K) 之间的整数组成的序列 ({A_1,...,A_N})（包括 (K)）。有 (K^N) 个这样的序列，求出 (gcd(A_1,...,A_N)) 的总和。由于此总和可能非常大，因此请取模 (10^9+7)。
传送门

分析：

  以 (dp[i]) 表示 (gcd) 为 (i) 的序列个数，([1,k]) 内 (i) 的倍数的个数为 (lfloor frac{k}{i} floor)。序列总数为：({lfloor frac{k}{i} floor}^n)，同时由于会出现重复，所以要减去 (gcd) 为 (i*2,i*3,...) 的情况，循环要从大到小。
  一开始直接减，发现有一部分多减了（具体见代码注释部分）。即当两个数均为 (i) 的倍数且倍数互质，那么二者的 (gcd) 仍为 (i)，即序列中不一定要出现 (i)。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e5+5;
ll dp[N];
ll power(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int main()
{
    int n,k;
    ll ans=0;
    scanf("%d%d",&n,&k);
    for(int i=k;i>=1;i--)//以i为gcd
    {
        int tk=k/i;
        dp[i]=power(1LL*tk,1LL*n);
        for(int j=i*2;j<=k;j+=i)
            dp[i]-=dp[j];
        //ll t=power(1LL*tk,1LL*n)-power(1LL*(tk-1),1LL*n);cout<<i<<"="<<t<<endl;
        ans=(ans+dp[i]*i%mod+mod)%mod;//cout<<ans<<endl;
    }
    printf("%lld
",ans);
    return 0;
}