试除法求一个数的所有约数

  1. vector<int> get_divisors(int n){
  2.     vector<int> res;
  3.     for (int i = 1; i <= n / i; i ++ ){
  4.         if(n % i == 0){
  5.             res.push_back(i);
  6.             if(i != n / i) res.push_back(n / i);
  7.         }
  8.     }
  9.     sort(res.begin(), res.end());
  10.     return res;
  11. }

约数个数

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. #include <vector>
  7. using namespace std;
  9. typedef long long ll;
  10. const int N = 110, mod = 1e9 + 7;
  12. int main()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     unordered_map<int, int> primes;
  18.     while (n -- ){
  19.         int x;
  20.         cin >> x;
  21.         for (int i = 2; i <= x / i; i ++ ){
  22.             while(x % i == 0){
  23.                 x /= i;
  24.                 primes[i]++;
  25.             }
  26.         }
  27.         if(x > 1) primes[x]++;
  28.     }
  29.     ll res = 1;
  30.     for(auto p : primes) res = res * (p.second + 1) % mod;
  31.     cout << res << endl;
  33.     return 0;
  34. }

约数之和

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. #include <vector>
  7. using namespace std;
  9. typedef long long ll;
  10. const int N = 110, mod = 1e9 + 7;
  12. int main()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     unordered_map<int, int> primes;
  18.     while (n -- ){
  19.         int x;
  20.         cin >> x;
  21.         for (int i = 2; i <= x / i; i ++ ){
  22.             while(x % i == 0){
  23.                 x /= i;
  24.                 primes[i]++;
  25.             }
  26.         }
  27.         if(x > 1) primes[x]++;
  28.     }
  29.     ll res = 1;
  30.     for(auto p : primes){
  31.         ll a = p.first, b = p.second;
  32.         ll t = 1;
  33.         while(b--) t = (t * a + 1) % mod;
  34.         res = res * t % mod;
  35.     }
  36.     cout << res << endl;
  37.     return 0;
  38. }

欧几里得算法/辗转相除法

  1. int gcd(int a, int b)  // 欧几里得算法
  2. {
  3.     return b ? gcd(b, a % b) : a;
  4. }