Codeforces Round #589 (Div. 2) C - Primes and Multiplication(数学, 质数)

链接:

https://codeforces.com/contest/1228/problem/C

题意:

Let's introduce some definitions that will be needed later.

Let prime(x) be the set of prime divisors of x. For example, prime(140)={2,5,7}, prime(169)={13}.

Let g(x,p) be the maximum possible integer pk where k is an integer such that x is divisible by pk. For example:

g(45,3)=9 (45 is divisible by 32=9 but not divisible by 33=27),

g(63,7)=7 (63 is divisible by 71=7 but not divisible by 72=49).

Let f(x,y) be the product of g(y,p) for all p in prime(x). For example:

f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10,

f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63.

You have integers x and n. Calculate f(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7).

思路:

对于x的每个质约数, 计算其在n!内的乘积总和.

先得到x的质约数, 对于每个质数p, 其在n!内存在n/p^1, n/p^2....因为算的时候不断累加后面, 所有算一边即可.

快速幂优化.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MOD = 1e9+7;

vector<int> Pri;

void Init(LL val)

{

    for (LL i = 2;i*i <= val;i++)

    {

        if (val%i == 0)

            Pri.push_back(i);

        while (val%i == 0)

            val /= i;

    }

    if (val != 1)

        Pri.push_back(val);

}

LL Cal(LL val, int p)

{

    //素数p在val的阶乘下的次方贡献

    LL cnt = 0;

    while (val)

    {

        cnt += val/p;

        val /= p;

    }

    return cnt;

}

LL QucikMi(LL a, LL b)

{

    LL res = 1;

    while (b)

    {

        if (b&1)

            res = (res*a)%MOD;

        a = (a*a)%MOD;

        b >>= 1;

    }

    return res;

}

int main()

{

    LL x, n;

    cin >> x >> n;

    Init(x);

    LL res = 1;

    for (int i = 0;i < Pri.size();i++)

    {

        LL cnt = Cal(n, Pri[i]);

        res = (res*(QucikMi(Pri[i], cnt)))%MOD;

    }

    cout << res%MOD << endl;

    return 0;

}