JZTXT

Codeforces Round 885 (Div. 2)E. Vika and Stone Skipping（数学，质因数分解）

发布时间 2023-08-28 12:26:40作者: XiCen

题目链接：https://codeforces.com/problemset/problem/1848/E

 

大致题意：

 

打水漂，某人在海岸线以 f （正整数）的力量扔出石头，会在f，f+（f-1），f+（f-1）+（f-2），........，f+（f-1）+.....+2+1，的位置接触水面；

 

现在给出坐标x和q次询问，每次询问给出一个y值，将x = x*y；假设石头在x的位置接触水面，问有多少种力量的可能？

 

答案模M，保证M是一个质数；

 

解题思路：

 

如果你对于数字比较敏感的话，那么应该会发现结果和x的奇因子个数有关；

 

下面贴个官方的证明（某佬翻译过来的）：

 

 

 

那么接下来，我们就需要记录x的奇因子的个数，这个可以用map来记录；

 

当然，这还不够，因为M可以比较小，那么就会出现奇因子个数是M的倍数，导致结果为0，然后那个奇因子下次增加后不是M倍数，但是因为答案上次是0，会导致一直是0，导致出错；

 

所以，我们需要额外的俩个变量来标记一下，具体可以看代码来理解一下；

 

时间复杂度：O（nlogn）；

 

代码：

#include<bits/stdc++.h>
#define int long long

int x, T, mod, ans, res, p;//p和res是额外的变量，与奇因子个数为M的倍数时相关处理有关
std::map<int, int>mp, pre;

const int N = 1e6 + 6;
int PRIME[N + 6];
std::vector<int> prime;

void KSFJZYS()//快速分解质因数
{
    for (int i = 2; i <= N; ++i)
    {
        if (!PRIME[i]) { PRIME[i] = i; prime.push_back(i); }
        for (auto p : prime)
        {
            if (p * i > N)break;
            PRIME[i * p] = p;
            if (i % p == 0)break;
        }
    }
}

int QPOW(int a, int b)
{
    int sum = 1;
    while (b)
    {
        if (b & 1)sum = sum * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return sum;
}

int inv(int a) { return QPOW(a, mod - 2); }

void GO(int a)
{
    std::map<int, int> m;
    while (a != 1)m[PRIME[a]]++, a /= PRIME[a];//本处是分解质因数

    for (auto [u, v] : m)//计算过程
    {
        if (u == 2 || v == 0)continue;
        int I = mp[u] + 1;
        //std::cout << u << " " << I << " " << v << "\n";
        ans = ans * inv(I) % mod;
        if ((I % mod) == 0)if ((p -= 1) == 0)ans = res;
        I += v;
        if ((I % mod) != 0 && p)res = res * I * ((I - v) % mod ? inv(I - v) : 1) % mod;
        if ((I % mod) == 0)res = res * inv(I - v) % mod, p++;
        //std::cout << p << " " << res << " " << ans << "s\n";
        ans = ans * I % mod;
        mp[u] = I - 1;
        if (ans)res = ans;
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    KSFJZYS();

    std::cin >> x >> T >> mod;
    ans = 1; res = 1;

    for (int i = 2; i * i <= x; ++i)
        while (x % i == 0)mp[i]++, x /= i;

    if (x != 1)mp[x]++;

    for (auto [u, v] : mp)if (u != 2)ans = ans * (v + 1) % mod;
    res = ans;

    while (T--)
    {
        int a = 0;
        std::cin >> a;

        GO(a);

        std::cout << ans << "\n";
    }

    return 0;
}

本题难点在于看出结果和x的奇因子个数有个，然后还要处理M这个模数比较小的问题：）