Description
Sol
这题好难啊QAQ
反正不看题解我对自然数幂求和那里是一点思路都没有qwq
先推出一个可做一点的式子：
\(f(n)=\sum_{k=1}^{n}[(n,k)=1]k^d\)
\(=\sum_{k=1}^{n}k^d\sum_{e|n,e|k}\mu(e)\)
\(=\sum_{e|n}\sum_{k=1}^{n/e}(ek)^d\mu(e)\)
\(=\sum_{e|n}e^d\mu(e)\sum_{k=1}^{n/e}k^d\)
我们假装（反正就是可以但是我太弱了不会证）后面的式子是一个d+1次的关于n的多项式，因为d很小所以我们用高斯消元求出来系数ai，之后得到：
原式
\(=\sum_{e|n}e^d\mu(e)\sum_{k=1}^{d+1}a_k(n/e)^k\)
\(=\sum_{k=1}^{d+1}a_k\sum_{e|n}e^d\mu(e)(n/e)^k\)
设\(fk(n)=\sum_{e|n}e^d\mu(e)(n/e)^k\)
因为\(e^d\mu(e)\)与\((n/e)^i\)都是积性函数，所以他们的狄利克雷卷积\(fk(n)\)也是积性函数
我们对于n分解质因数，对于每种质数的qi次幂单独计算，然后乘起来。
显然这样答案等于
\(1^d*\mu(1)*pi^{qi^{k}}+pi^d*\mu(pi)*p^{(qi-1)^{k}}\)
题目都帮你分解好了就是一种暗示qwq
看到乘数里面有莫比乌斯函数，就要往次幂上想，然后只保留零次幂和一次幂（逃
这个可以直接暴力，ai还是已知的，那么直接枚举d即可。
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll ans,v[105][105],pa[1005],pb[1005],P=1e9+7;int n,d;
ll ksm(ll a,ll b){ll res=1;for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;return res;}
void gauss(int n)
{
for(int i=1,k,t;i<=n;i++)
{
for(int j=i;j<=n;j++) if(v[j][i]) for(k=i;k<=n+1;k++) swap(v[j][k],v[i][k]);
for(int j=i+1;j<=n;j++) if(i!=j) for(t=1ll*v[j][i]*ksm(v[i][i],P-2)%P,k=i;k<=n+1;k++) v[j][k]=(v[j][k]-1ll*t*v[i][k]%P+P)%P;
}
for(int i=n;i;i--)
{
for(int j=n;j>i;j--) v[i][n+1]=(v[i][n+1]-1ll*v[i][j]*v[j][n+1]%P+P)%P;
v[i][n+1]=1ll*v[i][n+1]*ksm(v[i][i],P-2)%P;
}
}
int main()
{
scanf("%d%d",&d,&n);
for(int i=1;i<=d+1;i++)
{
for(int j=1;j<=d+1;j++) v[i][j]=ksm(i,j);
for(int j=1;j<=i;j++) v[i][d+2]=(v[i][d+2]+ksm(j,d))%P;
}
gauss(d+1);
for(int i=1;i<=n;i++) scanf("%lld%lld",&pa[i],&pb[i]);
for(int i=1,tmp=1;i<=d+1;i++,tmp=1)
{
for(int j=1;j<=n;j++) tmp=1ll*tmp*(ksm(pa[j],pb[j]*i)-ksm(pa[j],d+(pb[j]-1)*i)%P+P)%P;
ans=(ans+1ll*tmp*v[i][d+2]%P)%P;
}
printf("%lld\n",ans);
}