Codeforces 893E 数论

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;

const int N = 1000050;
const ll mod = 1e9 + 7;

template<class T>
T read()
{
    T x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9')  { if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch<= '9') { x = 10 * x + ch - '0'; ch = getchar();}
    return x * f;
}

ll fac[N], inv[N], q[N];
VI vec[N];

ll qpow(ll a, ll b, ll p)
{
    ll res = 1 % p;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void init()
{
    fac[1] = 1;
    for(int i = 2; i < N; ++i) fac[i] = fac[i - 1] * i % mod;
    q[0] = 1;
    for(int i = 1; i < N; ++i) q[i] = q[i - 1] * 2 % mod;
    inv[N - 1] = qpow(fac[N - 1], mod - 2, mod);
    for(int i = N - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
    for(int i = 2; i < N; ++i)
    {
        if(vec[i].empty())
            for(int j = i; j < N; j += i)
                vec[j].push_back(i);
    }
}

ll C(int m, int n)
{
    return fac[m] * inv[n] % mod * inv[m - n] % mod;
}

int main()
{
    init();
    int T = read<int>();
    while(T--)
    {
        int n = read<int>(), k = read<int>();
        ll ans = 1;
        for(auto u : vec[n])
        {
            int tmp = n, cnt = 0;
            while(tmp % u == 0)
            {
                ++cnt;
                tmp /= u;
            }
            ans = ans * C(cnt + k - 1, k - 1) % mod;;
        }
        ans = ans * q[k - 1] % mod;
        printf("%I64dn", ans);
    }
    return 0;
}

最后

以上就是平淡人生为你收集整理的Codeforces 893E 数论的全部内容，希望文章能够帮你解决Codeforces 893E 数论所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。