题解 D-变换

pj D 变换

感觉跟tgT1一个难度不甘心的同学可以先看Frist Step自己再想想

题面（我看到的版本）：

一个数不变，其他数乘上一个素数

Solution：

First Step：

既然是素数，肯定是与质因子有关，像位运算中将每一位分开讨论一样，有质因子也将每个质因子分开讨论（这是套路），一个确定的操作序列任意交换顺序都等价，所以不妨序列在一个质因子意义下相等后再考虑别的质因子

Second Step：

一个质因子意义下，每个数已经变成了它含这个质因子的次数，于是操作变为：每次将除一个数以外的所有数加1，这个操作不好处理，我们可以将它转化为所有数+1，任意一个位置的数-1（因为其实只进行了乘法，所以不必担心会不够减）（同样，这个转化也是比较套路的）

Third Step：

我们要做的就是利用这个操作磨平整个序列，“磨平”是相对关系，所以我们只关心让这个序列相对关系变化的操作：一个数-1，大家可以手模以下数据：

1 1 2 3 1 1

答案是将2 - 1、3 - 1 - 1，一共3次操作，也就是说，让序列所有数都变成最小数，就不需要再减了

所以答案为：

Fourth Step：

将每一个质因子的ans加起来即可，ans = 所有数的质因子数（可重）加起来 - 每一个质因子的最小次数 * n

总复杂度：

关于如何求这个答案，可以看代码，代码思路清晰、注释详细（就是有点长）

Code：

#include <bits/stdc++.h>
using namespace std;

const int MA = 1 << 23;
char buf[MA], *p1 = buf, *p2 = buf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MA, stdin), p1 == p2) ? EOF : *p1 ++)

inline int read()
{
    int ff = 0, rr = 1;
    char ch = gc();
    while(! isdigit(ch))
    {
        if(ch == '-') rr = -1;
        ch = gc();
    }
    while(isdigit(ch))
    {
        ff = (ff << 1) + (ff << 3) + (ch ^ 48);
        ch = gc();
    }
    return ff * rr;
}

void print(int x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
 // 1. 前面卡常的，不用看
const int N = 1e6 + 7;
 // 2.
int minv[N], pri[N], cnt; // minv[i]表示i的最小质因子，pri[i]表示第i个质数，cnt记录质数个数

inline void euler(int n = N - 6)
{
    for(int i = 2; i <= n; ++i)
    {
        if(! minv[i]) minv[i] = i, pri[++ cnt] = i;
        for(int j = 1; j <= cnt; ++j)
        {
            if(pri[j] * i > n) break;
            minv[pri[j] * i] = pri[j];
            if(i % pri[j] == 0) break;
        }
    }
}
 // 3. 从2~3是欧拉筛模板，就不写注释了
int n, b[N], c[N], vis[N];
// b[i]表示i这个数在整个序列中的最小次数（只用到了i是质数的部分数组）
// c[i]表示序列中第i个数的质因子个数（可重）
// vis[i]表示i这个数是否是每一个数的质因子（如果不是，它的b[]值一定为0，不用算）

inline void init() // 预处理一些数组，一会要用
{
    euler();
    n = read();
    for(int i = 1; i <= N - 6; ++i)
        b[i] = 30; // 每个质因子在单个数中的次数最大不会超过30（事实上达不到）
}

inline void work()
{
    for(int i = 1; i <= n; ++i)
    {
        int a = read();
        while(a != 1)
        // 利用已经处理好的minv数组O(loga)找出一个数质因子
        // 这和试除法一样是基操，可以背会
        {
            int now = 0, k = minv[a];
             // now表示a中minv[a]的次数
             // 这里的a和输入的a已经不一样了，minv[a]中的a指的是现在的a
             // 但minv[a]的次数没变

             // 因为后面a会变，所以用k先将minv[a]记录下来

            while(a % k == 0)
            {
                ++ now; // 找到次数
                a /= k;
            }
            ++ vis[k]; // 记录这个数出现的次数
            b[k] = min(b[k], now); // 按b[]定义来即可
            c[i] += now; // 每个质因子次数加起来即可
        }
    }
}

inline void calc()
{
    int ans = 0;

    for(int i = 1; i <= n; ++i) // 记录答案第一部分
        ans += c[i];

    for(int i = 1; i <= cnt; ++i) // 该减的减去
        if(vis[pri[i]] == n)
          // 如果一个数出现不到n次，肯定不减它因为b[]为0
          // 如果不这样，得到的b[]不是真实的b[]（在pri[i]一个数中没有出现但没有将次数标记为0）
            ans -= b[pri[i]] * n;

    print(ans);
}

signed main()
{
    init();
    work();
    calc();

    return 0;
}