约数

1
约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。在大学之前，"约数"一词所指的一般只限于正约数。约数和倍数都是二元关系的概念，不能孤立地说某个整数是约数或倍数。一个整数的约数是有限的。同时，它可以在特定情况下成为公约数。

试除法求约数

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100
1≤ai≤2×1e9

输入样例：

1
2
3
2
6
8

输出样例：

1
2
1 2 3 6 
1 2 4 8

代码

个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
	首先我们要明确约数的定义 诺 a * b = c 那么 a,b便是c的约数。
*/
#include<bits/stdc++.h>
using namespace std;
vector<int> get_divisors(int x) {
	vector<int>sm;
	vector<int>bi;
    // 我们遍历小的哪一个
	for(int i=1;i<=x/i;i++){
		if (x%i == 0) {
			sm.push_back(i);
			if (i != x/i) {
				bi.push_back(x/i);
			}
		}
	}
	for(int i=bi.size() - 1;i>=0;i--){
		sm.push_back(bi[i]);
	}
	return sm;
}
int main() {
	int n;cin>>n;
	while(n--){
		int val;cin>>val;
		vector<int> res = get_divisors(val);
		for(int i=0;i < res.size();i++){
			printf("%d ",res[i]);
		}
		cout<<endl;
		
	}	
}
/*
2
6
8
*/
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);

        for (auto x : res) cout << x << ' ';
        cout << endl;
    }

    return 0;
}

约数个数

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100,
1≤ai≤2×1e9

输入样例：

1
2
3
4
3
2
6
8

输出样例：

1
12

代码

个人代码(ps 个人不回找的解析)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
	我们不注最后的数据大小，我们想要得知的时他能被那些质数组合出来，找出这个数所有的零件，一个约数不过是有这些约数组成每一个零件可以取（0-n）也就是 零件个数加一 零件全是质数没法互相组合也就是唯一的所以约数的个数便是所有（n+1）的之积

*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N  = 1000000007;
int main() {
	map<int, int>record;
    // 记录每一个零件的个数
	int n;
	cin >> n;
	while (n--) {
		int val;
		cin >> val;
		for (int i = 2; i <= val / i; i++) {
			while (val % i == 0) {
				val /= i;
				record[i]++;
			}
            // 将此零件放入
		}
        // 判断最后是否是一个质数
		if (val != 1) {
			record[val]++;
		}
	}
	ll res = 1;
	map<int, int>::iterator i = record.begin();
	for (i = record.begin(); i != record.end(); i++) {
		res = ((i->second + 1) * (res)) % N; 
	}
	cout<<res<<endl;
}
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    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] ++ ;
    }

    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;

    cout << res << endl;

    return 0;
}

约数之和

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100,
1≤ai≤2×109

输入样例：

1
2
3
4
3
2
6
8

输出样例：

1
252

代码

个人代码（错误）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
	思路：首先先把数据拆成零件遍历所有零件 对于遍历到i 我们有到i-1的所有约数之和对于i我们可以取 0 - i^n 也就是说当我们取 某一个值得时候对应得可以得到得余数之和 为 (1 + i + i*i + ..... + i^n) * record[i-1], 依次我们可以得到答案。
	但是注意这个数据很大中间环节很有可能出现越界的情况应该小心应对

*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e9+7;

int main() {
	map<ll,int> record;
	int n;cin>>n;
	while(n--){
		ll val;cin>>val;
		for(ll i=2;i<=val/i;i++){
			while(val%i == 0) {
				record[i]++;
				val/=i;
			}
		}
		if (val != 1) {
			record[val]++;
		}
	}
	
	map<ll,int>::iterator i;
	ll res = 1;
	for(i = record.begin();i!=record.end();i++){
		
		ll cur = 1;
		ll ans = 1;
		for(int j=0;j<i->second;j++){
		// 个人就是没考虑这里导致数据越界gg了
            cur *= i->first;
			ans += cur;
		}
		res *= ans;
		res %= N;
	}
	cout<<res<<endl;
	
}
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    int n;
    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] ++ ;
    }

    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        // 这里相当于把之前的和全都右移一位加上一个 a^0
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

Gcd函数

gcd函数的原理是基于欧几里得算法，也被称为辗转相除法。这个算法的基本思想是利用两个整数a和b（a > b）的最大公约数等于b和a%b的最大公约数。

具体地说，我们可以用以下的步骤来计算a和b的最大公约数gcd(a, b)：

  1. 用b去除a，得到商q和余数r，即a = bq + r，其中0 <= r < b；
  2. 如果r等于0，则gcd(a, b) = b；
  3. 否则，将b赋值为r，将a赋值为b，然后返回第1步。

举个例子来说，假设我们要计算gcd(24, 36)，则按照上述步骤可以得到：

  • 36 = 24 * 1 + 12；
  • 24 = 12 * 2 + 0。

因此，gcd(24, 36) = 12。

欧几里得算法的正确性可以通过数学归纳法来证明。具体来说，我们可以证明，对于任意两个正整数a和b，欧几里得算法可以找到它们的最大公约数。证明的核心思想是，如果d是a和b的公约数，则d也是b和a%b的公约数。因此，如果d是a和b的最大公约数，则d也是b和a%b的最大公约数。根据这个思想，我们可以得出结论，欧几里得算法可以计算出a和b的最大公约数。

在实际编程中，可以使用循环或递归的方式来实现欧几里得算法。递归实现方式如下：