约数及约数个数，约数乘积的计算

869. 试除法求约数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定 n

个正整数 ai，对于每个整数 ai

，请你按照从小到大的顺序输出它的所有约数。

输入格式

第一行包含整数 n

。

接下来 n

行，每行包含一个整数 ai

。

输出格式

输出共 n

行，其中第 i 行输出第 i 个整数 ai

的所有约数。

数据范围

1≤n≤100

,
2≤ai≤2×109

输入样例：

2
6
8

输出样例：

1 2 3 6 
1 2 4 8 

/**
 * 对于一个数的约数，一般都是成双成对的出现，除了完全平方数的因子只
 * 有一个；
 * 所以我们可以只算小于sqrt(val)的因子d，大于sqrt(val)的因子可以直接
 * 用val/d算出来。
*/
 
#include 
#include 
 
using namespace std;
 
set<int> get_divisors(int val)
{
    set<int> res;
    for(int i=1;i<=val/i;++i)
    {
        if(val%i==0)
        {
            res.insert(i);
            if(val/i!=i)
                res.insert(val/i);
        }
    }
    return res;
}
 
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int val;
        cin >> val;
        set<int> res=get_divisors(val);
        for(auto a:res)
            cout << a << ' ';
        cout << endl;
    }
    return 0;
}

870. 约数个数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定 n

个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7

取模。

输入格式

第一行包含整数 n

。

接下来 n

行，每行包含一个整数 ai

。

输出格式

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

取模。

数据范围

1≤n≤100

,
1≤ai≤2×109

输入样例：

3
2
6
8

输出样例：

12

 

 * 任何一个正整数n都能写成若干个质因子相乘的结果；
 * 对于一个正整数n的质因子分解为各质因子Pi的个数分别为e1,e2,...,ek;
 * 则n的约数个数为(e1+1)*(e2+1)*...*(ek+1);

/**
 * 任何一个正整数n都能写成若干个质因子相乘的结果；
 * 对于一个正整数n的质因子分解为各质因子Pi的个数分别为e1,e2,...,ek;
 * 则n的约数个数为(e1+1)*(e2+1)*...*(ek+1);
*/
 
#include 
#include 
 
using namespace std;
 
typedef long long ll;
const int mod= 1e9+7;
 
int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> ump;
    while(n--)
    {
        int val;
        cin >> val;
        for(int i=2;i<=val/i;++i)
        {
            if(val%i==0)
            {
                while(val%i==0)
                {
                    ump[i]++;
                    val/=i;
                }
            }
        }
        if(val>1)
            ump[val]++;
    }
    
    ll res=1;
    for(auto a:ump)
        res=res*(a.second+1)%mod;
    cout << res << endl;
    return 0;
}

871. 约数之和

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定 n

个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7

取模。

输入格式

第一行包含整数 n

。

接下来 n

行，每行包含一个整数 ai

。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7

取模。

数据范围

1≤n≤100

,
1≤ai≤2×109

输入样例：

3
2
6
8

输出样例：

252

 coding:

 * 任何一个正整数n都能写成若干个质因子相乘的结果；
 * 对于一个正整数n的质因子分解为各质因子Pi的个数分别为e1,e2,...,ek;
 * 则n的约数之和为

(1+p1+p1^2+...+p1^e1)+(1+p2kp2^2+...+p2^e2)+...+(1+pk+pk^2+...+pk^ek);

/**
 * 任何一个正整数n都能写成若干个质因子相乘的结果；
 * 对于一个正整数n的质因子分解为各质因子Pi的个数分别为e1,e2,...,ek;
 * 则n的约数之和为
 * (1+p1+p1^2+...+p1^e1)+(1+p2kp2^2+...+p2^e2)+...+(1+pk+pk^2+...+pk^ek);
*/
 
#include 
#include 
 
using namespace std;
 
typedef long long ll;
const int mod= 1e9+7;
 
int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> ump;
    while(n--)
    {
        int val;
        cin >> val;
        for(int i=2;i<=val/i;++i)
        {
            if(val%i==0)
            {
                while(val%i==0)
                {
                    ump[i]++;
                    val/=i;
                }
            }
        }
        if(val>1)
            ump[val]++;
    }
    
    ll res=1;
    for(auto a:ump)
    {
        int f=a.first,s=a.second;
        ll t=1;
        while(s--)  t=(t*f+1)%mod;
        res=res*t%mod;
    }
    
    cout << res << endl;
    return 0;
}

872. 最大公约数

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

给定 n

对正整数 ai,bi

，请你求出每对数的最大公约数。

输入格式

第一行包含整数 n

。

接下来 n

行，每行包含一个整数对 ai,bi

。

输出格式

输出共 n

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

数据范围

1≤n≤105

,
1≤ai,bi≤2×109

输入样例：

2
3 6
4 6

输出样例：

3
2

 coding:

#include 
#include 
 
using namespace std;
 
 
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
 
int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a,b;
        cin >> a >> b;
        cout << gcd(a,b) << endl;
    }
    return 0;
}