最近心情不好所以写代码来获得快落
4级题有点难做？然后就开始挑简单的5级题开始写
然后准备记录一些自己没有做出来
参考讨论区或者博客才做出来的题目
这个题参考了讨论区
令 t = n!
1/t = 1/x + 1/y , 0 < x <= y 的正整数解计数， n <= 1e6
考虑对式子进行变换
1/t = (x + y) / xy
xy = t * (x + y)
我们这时候应该有一个反应，配方有
(x - t) * (y - t) = t * t
所以考虑统计 t * t 的因子数就可以了
分解质因数即可
1 n, m, k = int(input()), 1, 1000000007 2 v = [0 for i in range(n + 1)] 3 p = [0 for i in range(n + 1)] 4 for i in range(2, n + 1): 5 if not v[i]: 6 p[0] += 1 7 p[p[0]] = i 8 t, j = 1, i 9 while j <= n:10 t += n // j * 211 j *= i12 m = m * t % k 13 for j in range(1, p[0] + 1):14 if i * p[j] > n:15 break16 v[i * p[j]] = 117 if i % p[j] == 0:18 break19 print ((m + 1) * pow(2, k - 2, k) % k)
这个题参考了博客
考虑 i 存在于原集合的条件
假设 i 的倍数 s = {a * i, b * i, c * i ... } 存在于输入给定的集合中
那么我们知道 d = gcd(a, b)，d * i 肯定是存在于原集合中的
那么必然存在 e = gcd(c, d)，e * i 也存在于原集合中
即 gcd(a, b, c ...) * i 必然存在于原集合中
因为 i 要存在于原集合中只能依靠 s 中的元素
又有gcd(s) >= 1 * i
所以当且仅当 gcd(s) == i 的时候
才有 i 存在于原集合
枚举 i 即可
1 #include2 3 using namespace std; 4 5 const int N = 1e6 + 5; 6 7 int n, m, k, b[N]; 8 9 int main() {10 ios::sync_with_stdio(false);11 cin >> n;12 for (int x, i = 1; i <= n; i ++) {13 cin >> x, k = max(x, k);14 if (!b[x]) b[x] = 1, m ++; 15 }16 for (int i = 1; i <= k; i ++) 17 if (!b[i]) {18 int t = 0;19 for (int j = i << 1; j <= k; j += i)20 if (b[j])21 t = __gcd(t, j);22 if (t == i) m ++;23 }24 cout << m;25 return 0;26 }
傻屌题目，考虑a[x] +y
那么对b的x, 2x,3x..产生贡献
那么对c的kx，容易发现贡献次数为f(k)，f(k)为k的因数个数
考虑到x是随机的，所以采用每次更新的时候O(n / x)更新
查询O(1)回答的话，期望每次更新次数是O(logn)的，成了
垃圾题目，c++ 提交的话，要开快读和快速输出...
visual c++提交的话，直接scanf + printf就成了...
1 #include2 3 const int N = 1e6 + 5; 4 5 int n, m, a[N]; 6 7 long long b[N]; 8 9 int main() {10 int op, x, y;11 scanf("%d %d", &n, &m);12 for (int i = 1; i <= n; i ++)13 for (int j = i; j <= n; j += i)14 a[j] += 1;15 while (m --) {16 scanf("%d %d", &op, &x);17 if (op == 1) {18 scanf("%d", &y);19 for (int i = 1, j = x; j <= n; i ++, j += x) 20 b[j] += y * a[i];21 }22 else printf("%lld\n", b[x]);23 }24 return 0;25 }