C++ 数论相关题目（约数）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++ 数论相关题目（约数）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、试除法求约数

给定 n
个正整数 ai
，对于每个整数 ai
，请你按照从小到大的顺序输出它的所有约数。

输入格式
第一行包含整数 n
。

接下来 n
行，每行包含一个整数 ai
。

输出格式
输出共 n
行，其中第 i
行输出第 i
个整数 ai
的所有约数。

数据范围
1≤n≤100
,
1≤ai≤2×109
输入样例：
2
6
8
输出样例：
1 2 3 6
主要还是可以成对的求约数进行优化，不然会超时。
时间复杂度根号n

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;

vector<int> solve(int a)
{
    vector<int> res;
    for(int i = 1; i <= a / i; i ++ )
    {
        if(a % i == 0)
        {
            res.push_back(i);
            if(a / i != i)
                res.push_back(a / i);
        }
    }
    sort(res.begin(), res.end());

    return res;
}


int main ()
{
    cin>>n;
    while(n -- )
    {
        int a;
        cin>>a;
        auto t = solve(a);
        for(auto x : t)
            cout<<x<<' ';
        cout<<endl;
    }
    
    return 0;
}

2、约数个数

给定 n
个正整数 ai
，请你输出这些数的乘积的约数个数，答案对 109+7
取模。

输入格式
第一行包含整数 n
。

接下来 n
行，每行包含一个整数 ai
。

输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7
取模。

数据范围
1≤n≤100
,
1≤ai≤2×109
输入样例：
3
2
6
8
输出样例：
12
主要是要理解算术基本定理：
C++ 数论相关题目（约数）,数论,算法笔记,力扣,c++,算法
约数个数：（a1+1）(a2+2)…(an+n)
代码思想：先对每个数进行质因数分解，然后利用约数个数公式进行计算。

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int n;

int main ()
{
    cin >> n;
    unordered_map<int, int> primes;
    while(n -- )
    {
      int x;
      cin >> x;
      
      for(int i = 2; i <= x / i; i ++ )
      {
          while(x % i == 0)
          {
              x /= i;
              primes[i] ++;
          }
      }
      if(x > 1) primes[x] ++;
      
    }
    long long res = 1;
    for(auto prime : primes)
        res = res * (prime.second + 1) % mod;
        
    cout << res << endl;
    
    return 0;
}

3、约数之和

给定 n
个正整数 ai
，请你输出这些数的乘积的约数个数，答案对 109+7
取模。

输入格式
第一行包含整数 n
。

接下来 n
行，每行包含一个整数 ai
。

输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7
取模。

数据范围
1≤n≤100
,
1≤ai≤2×109
输入样例：
3
2
6
8
输出样例：
12
数论的题目还是主要是记公式：
C++ 数论相关题目（约数）,数论,算法笔记,力扣,c++,算法

因此，这里我们先质因数分解出底数和指数，然后对每个对底数和指数求一个括号内的数，然后累乘到答案上即可。

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;
int n;

int main ()
{
    cin >> n;
    
    unordered_map<int, int> primes;
    
    while(n -- )
    {
        int x;
        cin >> x;
        
        for(int i = 2; i <= x / i; i ++ )
        {
            while(x % i == 0)
            {
                x /= i;
                primes[i] ++;
            }
        }
        if(x > 1) primes[x] ++;
    }
    
    long long res = 1;
    
    for(auto prime : primes)
    {
        long long t = 1;
        long long p = prime.first, a = prime.second;
        while(a -- )
        {
            t = (t * p + 1) % mod;
        }
        res = res * t % mod;
    }
    
    cout << res << endl;
    
    return 0;
}

4、最大公约数

给定 n
对正整数 ai,bi
，请你求出每对数的最大公约数。

输入格式
第一行包含整数 n
。

接下来 n
行，每行包含一个整数对 ai,bi
。

输出格式
输出共 n
行，每行输出一个整数对的最大公约数。

数据范围
1≤n≤105
,
1≤ai,bi≤2×109
输入样例：
2
3 6
4 6
输出样例：
3

主要是记模板，a和b的最大公约数等于b和a模b的最大公约数。文章来源地址https://www.toymoban.com/news/detail-806141.html

#include <iostream>

using namespace std;

int n;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main ()
{
    cin >> n;
    while(n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) <<endl;
    }
    
    return 0;
}