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
主要還是可以成對的求約數進行優(yōu)化，不然會超時。
時間復雜度根號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
主要是要理解算術基本定理：

約數個數：（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
數論的題目還是主要是記公式：

因此，這里我們先質因數分解出底數和指數，然后對每個對底數和指數求一個括號內的數，然后累乘到答案上即可。

#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的最大公約數。文章來源地址http://www.zghlxwxcb.cn/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;
}

到了這里，關于C++ 數論相關題目（約數）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！