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; }