数论 - 约数基础 【 试除法求所有约数 + 约数个数和约数之和
}
sort(ans,ans+cnt);
}
int main()
{
int n;
cin >> n;
while (n--)
{
cnt = 0;
int x;
cin >> x;
get_divisors(x);
for (int i = 0; i < cnt; i++)
{
cout << ans[i] << ' ';
}
cout << endl;
}
return 0;
}
[](
)(2)AcWing -870. 约数个数
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2?109
输入样例：
3
2
6
8
输出样例：
12
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<unordered_map> //无序映射
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
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) //i 为约数
{
x /= i;
primes[i]++; //统计每个约数的个数
}
}
if (x > 1) primes[x]++; //如果还没分解清,说明剩下的这个数是它的因数且只有一个
}
ll ans = 1;
for (auto prime : primes)
{
ans = ans * (prime.second + 1) % mod;//约数个数=(a1+1)(a2+1)...(ak+1)
}
cout << ans << endl;
return 0;
}
[](
)(3)AcWing- 871. 约数之和
给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2?109
输入样例：
3
2
6
8
输出样例：
252
代码
#include<iostream>
#include<algorithm>
#include<unordered_map> //无序映射
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
unordered_map<int, int >primes;
int main()
{
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i++)
{
while (x%i == 0) //i 为约数
{
x /= i;
primes[i]++; //统计每个约数的个数
}
}
if (x > 1) primes[x]++; //如果还没分解清,说明剩下的这个数是它的因数且只有一个
}
ll ans = 1;
for (auto prime : primes)
{
ll t = 1;
int p = prime.first, a = prime.second; //p 为约数，a 为约数的个数
while (a--)
{
t = (t*p + 1) % mod;//约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)
}
ans = (ans*t) % mod;
}
cout << ans << endl;
return 0;
}
[](
)(4)AcWing -872. 最大公约数
给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数对 ai,bi。
输出格式
输出共 n 行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤105,
1≤ai,bi≤2?109
输入样例：
2
3 6
4 6
输出样例：
3
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论