51nod挑的部分5级题

最近心情不好所以写代码来获得快落

4级题有点难做？然后就开始挑简单的5级题开始写

然后准备记录一些自己没有做出来

参考讨论区或者博客才做出来的题目

51nod_1189 阶乘分数

这个题参考了讨论区

令 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 的因子数就可以了

分解质因数即可

 n, m, k = int(input()), 1, 1000000007

 v = [0 for i in range(n + 1)]

 p = [0 for i in range(n + 1)]

 for i in range(2, n + 1):

     if not v[i]:

         p[0] += 1

         p[p[0]] = i

         t, j = 1, i

         while j <= n:

             t += n // j * 2

             j *= i

         m = m * t % k

     for j in range(1, p[0] + 1):

         if i * p[j] > n:

             break

         v[i * p[j]] = 1

         if i % p[j] == 0:

             break

 print ((m + 1) * pow(2, k - 2, k) % k)

51nod_1616 最小集合

这个题参考了博客

考虑 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 即可

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 1e6 + ; 

 int n, m, k, b[N];

 int main() {

     ios::sync_with_stdio(false);

     cin >> n;

     for (int x, i = ; i <= n; i ++) {

         cin >> x, k = max(x, k);

         if (!b[x]) b[x] = , m ++;

     }

     for (int i = ; i <= k; i ++)

         if (!b[i]) {

             int t = ;

             for (int j = i << ; j <= k; j += i)

                 if (b[j])

                     t = __gcd(t, j);

             if (t == i) m ++;

         }

     cout << m;

     return ;

 }

51nod_1586 约数和

傻屌题目，考虑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就成了...

 #include <stdio.h>

 const int N = 1e6 + ; 

 int n, m, a[N];

 long long b[N];

 int main() {

     int op, x, y;

     scanf("%d %d", &n, &m);

     for (int i = ; i <= n; i ++)

         for (int j = i; j <= n; j += i)

             a[j] += ;

     while (m --) {

         scanf("%d %d", &op, &x);

         if (op == ) {

             scanf("%d", &y);

             for (int i = , j = x; j <= n; i ++, j += x)

                 b[j] += y * a[i];

         }

         else printf("%lld\n", b[x]);

     }

     return ;

 }

巴特西

51nod挑的部分5级题

最新文章

热门文章