• 数论练习题

    1.Divisor SummationSPOJ - DIVSUM

    题意：求n的所有因子和    （O(N*logN))调和级别

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. #define mp make_pair
    4. #define pb push_back
    5. #define all(a) a.begin(), a.end()
    6. #define rep(i, a, n) for (int i = a; i <= n; i++)
    7. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    8. #define eps 1e-8
    9. #define zero(x) (((x) > 0 ? (x) : -(x)) < eps)
    10. using namespace std;
    11. const int maxn = 1e6 + 10;
    12. int n, m,d[maxn];
    13.  
    14. signed main()
    15. {
    16.     // freopen(".in", "r", stdin);
    17.     // freopen(".out", "w", stdout);
    18.     //  ios::sync_with_stdio(false);
    19.     for (int i = 1; i <= 500000; i++)
    20.     {
    21.         for (int j = 2 * i; j <= 500000; j += i)
    22.         {
    23.             d[j] += i;
    24.         }
    25.     }
    26.     int t;
    27.     cin >> t;
    28.     while (t--)
    29.     {
    30.         int n;
    31.         cin >> n;
    32.         cout << d[n] << endl;
    33.     }
    34.     return 0;
    35. }

    2.GCD LCM

    UVA - 11388

    题意：给出LCM与GCD,求最小符合的数a,b

     由GCD(a,b) | LCM(a,b)

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. #define mp make_pair
    4. #define pb push_back
    5. #define all(a) a.begin(), a.end()
    6. #define rep(i, a, n) for (int i = a; i <= n; i++)
    7. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    8. #define eps 1e-8
    9. #define zero(x) (((x) > 0 ? (x) : -(x)) < eps)
    10. using namespace std;
    11. const int maxn = 1e6 + 10;
    12. int n, m;
    13.  
    14. signed main()
    15. {
    16.     int t;
    17.     cin >> t;
    18.     while (t--)
    19.     {
    20.         int a, b;
    21.         cin >> a >> b;
    22.         if (b % a != 0)
    23.             cout << -1 << endl;
    24.         else
    25.             cout << a << ' ' << b << endl;
    26.     }
    27.     return 0;
    28. }

    3.Modified GCD

    CodeForces - 75C

    题意：给出a,b，给出区间l,r，求[l,r]中a,b的最大公约数

    求出gcd(a,b)的所有因子，然后二分查找即可

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. #define mp make_pair
    4. #define pb push_back
    5. #define all(a) a.begin(), a.end()
    6. #define rep(i, a, n) for (int i = a; i < n; i++)
    7. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    8. using namespace std;
    9. const int maxn = 1e6 + 10;
    10. vector<int> v;
    11.  
    12. signed main()
    13. {
    14.     int n, m;
    15.     cin >> n >> m;
    16.     int g = __gcd(n, m);
    17.     for (int i = 1; i * i <= g; i++)
    18.     {
    19.         if (g % i == 0)
    20.         {
    21.             v.pb(i);
    22.             if (i * i != g)
    23.                 v.pb(g / i);
    24.         }
    25.     }
    26.     sort(all(v));
    27.     int q;
    28.     cin >> q;
    29.     while (q--)
    30.     {
    31.         int l, r;
    32.         cin >> l >> r;
    33.         auto ans = upper_bound(v.begin(), v.end(), r) - 1;
    34.         if ((*ans) >= l && (*ans) <= r)
    35.             cout << *ans << endl;
    36.         else
    37.             cout << -1 << endl;
    38.     }
    39.     return 0;
    40. }

    4.Chef and KeyboardCodeChef - CHEFKEY 

    题意：给出n,m,c。找出满足a<n,b<m,a*b==c的(a,b)对数

    枚举c的所有因子

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. #define mp make_pair
    4. #define pb push_back
    5. #define all(a) a.begin(), a.end()
    6. #define rep(i, a, n) for (int i = a; i < n; i++)
    7. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    8. #define eps 1e-8
    9. #define zero(x) (((x) > 0 ? (x) : -(x)) < eps)
    10. using namespace std;
    11. const int maxn = 1e6 + 10;
    12. signed main()
    13. {
    14.     // freopen(".in", "r", stdin);
    15.     // freopen(".out", "w", stdout);
    16.     //  ios::sync_with_stdio(false);
    17.     int t;
    18.     cin >> t;
    19.     while (t--)
    20.     {
    21.         int n, m, c;
    22.         cin >> n >> m >> c;
    23.         int ans = 0;
    24.         for (int i = 1; i < sqrt(c); i++)
    25.         {
    26.             if (c % i == 0 && i <= n && c / i <= m)
    27.                 ans++;
    28.         }
    29.         for (int i = 1; i < sqrt(c); i++)
    30.         {
    31.             if (c % i == 0 && i <= m && c / i <= n)
    32.             {
    33.                 ans++;
    34.             }
    35.         }
    36.         if ((int)sqrt(c) * (int)sqrt(c) == c && (int)sqrt(c) <= n && (int)sqrt(c) <= m)
    37.         {
    38.             ans++;
    39.         }
    40.         cout << ans << endl;
    41.     }
    42.     return 0;
    43. }

    5.LCM CardinalityUVA - 10892 

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. #define mp make_pair
    4. #define pb push_back
    5. #define all(a) a.begin(), a.end()
    6. #define rep(i, a, n) for (int i = a; i <= n; i++)
    7. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    8. #define eps 1e-8
    9. #define zero(x) (((x) > 0 ? (x) : -(x)) < eps)
    10. using namespace std;
    11. const int maxn = 1e6 + 10;
    12. int n, m;
    13.  
    14. signed main()
    15. {
    16.     while (cin >> n)
    17.     {
    18.         if (n == 0)
    19.             return 0;
    20.         cout << n << " ";
    21.         int ans = 1;
    22.         for (int i = 2; i <= n; i++)
    23.         {
    24.             int cnt = 0;
    25.             while (n % i == 0)
    26.             {
    27.                 cnt++;
    28.                 n /= i;
    29.             }
    30.             if (cnt)
    31.             {
    32.                 ans *= (cnt * 2 + 1);
    33.             }
    34.         }
    35.         if (n > 1)
    36.             ans *= 3;
    37.         cout << (ans + 1) / 2 << endl;
    38.     }
    39.     return 0;
    40. }

    6.H(n)

     UVA - 11526 

    整除分块

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. #define mp make_pair
    4. #define pb push_back
    5. #define all(a) a.begin(), a.end()
    6. #define rep(i, a, n) for (int i = a; i <= n; i++)
    7. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    8. #define eps 1e-8
    9. #define zero(x) (((x) > 0 ? (x) : -(x)) < eps)
    10. using namespace std;
    11. const int maxn = 1e6 + 10;
    12. int n, m;
    13.  
    14. signed main()
    15. {
    16.     int t;
    17.     cin >> t;
    18.     while (t--)
    19.     {
    20.         int n;
    21.         cin >> n;
    22.         int ans = 0;
    23.         for (int l = 1, r; l <= n; l = r + 1)
    24.         {
    25.             r = n / (n / l);
    26.             ans += n / l * (r - l + 1);
    27.         }
    28.         cout << ans << endl;
    29.     }
    30.     return 0;
    31. }

    7.Calculation 2

    HDU - 3501

    题意 ：求小于n且与n不互质的数的和

    首先欧拉函数Euler(n)是求小于n且与n互质的数的个数，再有gcd的性质：如果gcd(n,i)=1,则gcd(n,n-i)=1

    那么，可以看做在[1，n-1]中与n互质的数是成对出现的，即如果i与n互质，则(n-i)也与n互质（Euler（n）为偶数）。而且可以发现这对数（i与n-i）的和为n。

    进一步得到结论：小于n且与n互质的数的和为n*Euler（n）/2；

    那么对于此题课先求1~n的和，再减去n*Euler（n）/2

    原创：

    hdu - 3501 - Calculation 2-（欧拉函数求互质数的和）_菜圾的博客-CSDN博客

    1. #include <bits/stdc++.h>
    2. #define int long long
    3. #define mp make_pair
    4. #define pb push_back
    5. #define all(a) a.begin(), a.end()
    6. #define rep(i, a, n) for (int i = a; i < n; i++)
    7. #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    8. #define eps 1e-8
    9. #define zero(x) (((x) > 0 ? (x) : -(x)) < eps)
    10. using namespace std;
    11. const int maxn = 1e6 + 10;
    12. const int mod = 1e9 + 7;
    13.  
    14. int st[maxn], pri[maxn], phi[maxn], cnt;
    15. int a[maxn], b[maxn];
    16.  
    17. void init()
    18. {
    19.     for (int i = 2; i < maxn; i++)
    20.     {
    21.         if (!st[i])
    22.         {
    23.             pri[cnt++] = i;
    24.             phi[i] = i - 1;
    25.         }
    26.         for (int j = 0; pri[j] * i < maxn; j++)
    27.         {
    28.             st[pri[j] * i] = 1;
    29.             if (i % pri[j] == 0)
    30.             {
    31.                 phi[i * pri[j]] = phi[i] * pri[j];
    32.                 break;
    33.             }
    34.             phi[i * pri[j]] = phi[i] * (pri[j] - 1);
    35.         }
    36.     }
    37. }
    38.  
    39. int eular(int x)
    40. {
    41.     int res = x;
    42.     for (int i = 2; i <= x / i; i++)
    43.         if (x % i == 0)
    44.         {
    45.             res = res / i * (i - 1);
    46.             while (x % i == 0)
    47.                 x /= i;
    48.         }
    49.     if (x > 1)
    50.         res = res / x * (x - 1);
    51.  
    52.     return res;
    53. }
    54.  
    55. signed main()
    56. {
    57.     int n;
    58.     while (cin >> n)
    59.     {
    60.         if (n == 0)
    61.             break;
    62.         int x = eular(n);
    63.         int ans = (n * (n - 1) / 2) % mod;
    64.         ans = (ans - (n * eular(n) / 2) % mod + mod) % mod;
    65.         cout << ans << endl;
    66.     }
    67.     system("pause");
    68. }

  • 相关阅读:
    jquery实现下拉框
    电脑重装系统后DirectX12旗舰版禁用了怎么解决？
    Spring 注解的诠释
    x86平台SIMD编程入门(1)：SIMD基础知识
    最难的IB课程为什么含金量最高？
    高可用组件，Keepalived详解
    125道Python面试题总结
    飞书中板栗看板适合做复杂任务管理吗
    DRF JWT认证（二）
    利用MySQL主从复制延迟拯救误删数据
  • 原文地址：https://blog.csdn.net/weixin_51198300/article/details/125583988