积性函数+筛法的思想计算-526互联

积性函数

f(ab)=f(a)*f(b)
链接：https://ac.nowcoder.com/acm/contest/53485/I

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

const int mod = 1000000007;

const int N = 2e7 + 10;

ll n, k;
int prime[N], f[N], g[N],cnt;
bool isprime[N];

int qmi(int x,ll k,int mod)
{
    int ans = 1;
    while(k)
    {
        if(k&1)
            ans = ans * 1ll * x % mod;
        x = 1ll * x * x % mod;
        k >>= 1;
    }
    return ans;
}

int main()
{
    cin >> n >> k;
    ll ans = 1;
    int up = k % (mod - 1);
    for (int i = 2; i <= n;i++)
    {
        if(!isprime[i])
        {
            prime[cnt++] = i;
            f[i] = qmi(i, k, mod);
            g[i] = __gcd(1ll * i, k);
        }
        for (int j = 0; 1ll * i * prime[j] <= n;j++)
        {
            isprime[i*prime[j]] = 1;
            f[i * prime[j]] = 1ll * f[i] * f[prime[j]] % mod;
            if(i%prime[j]==0)
            {
                g[i * prime[j]] = g[i];
                if(k/g[i]%prime[j]==0)
                    g[i * prime[j]] *= prime[j];
                break;
            }
            g[i * prime[j]] = g[i] * g[prime[j]];
        }
        ans = (ans + 1ll * f[i] * g[i] )% mod;
    }
    cout << ans;
}