试除法求约数
题目描述：
给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
输入格式:
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式:
输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。
数据范围:
1≤ n ≤100
2≤ ai ≤2×10^9
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8 解题代码：
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
vector <int> divisor(int x)
{
vector <int>res;
for (int i = 1;i<=x/i;i++)//将i<=sqrt(n)作为分界点，约数平均的分配在sqrt(n)两侧
{
if (x % i == 0)
{
res.push_back(i);//sqrt(n)左侧约数
if (x / i != i)//当x/i=i时i*i=x为防止i约数重复加入，所以需要加判断条件
{
res.push_back(x / i);//sqrt(n)右侧约数
}
}
}
sort(res.begin(), res.end());
return res;
}
int main()
{
int n;
cin >> n;
while(n--)
{
int x;
cin >> x;
auto res=divisor(x);
for (auto a : res)
{
cout << a << " ";
}
cout << endl;
}
return 0;
}
约数个数
题目描述：
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。
输入格式:
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式:
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7 取模。
数据范围:
1≤ n ≤100,
1≤ ai ≤2×10^9
输入样例：
3
2
6
8
输出样例：
12思路：
基于算术基本定理
N = (p1^x1)(p2^x2)(p3^x3)…(pk^xk) 其中p为质因子
约数个数=(x1+1)(x2+1)(x3+1)…(xk+1)
例如：
24=2 * 2 * 2 * 3=2^3 * 3
用各个质因子的指数加一后再相乘即为此数的约数个数
比如 (3+1)*(1+1)=4*2=8， 即表示24有8个约数。
24的约数:1、2、3、4、6、8、12、24
1.先求出并存好各质因子的指数
for(int i=2;i<=a/i;i++)
{
while(a%i==0)
{
a /= i;
primes[i]++;
}
}
if(a!=1)
{
primes[a]++;
}2.然后将质因子指数加一相乘并膜上mod得到结果
long long int res = 1;
for(auto p : primes) res = res * (p.second + 1) % mod;解题代码：
# include <iostream>
# include <unordered_map>
using namespace std;
const int mod= 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int>primes;
while(n--)
{
int a;
cin >> a;
for(int i=2;i<=a/i;i++)
{
while(a%i==0)
{
a /= i;
primes[i]++;
}
}
if(a!=1)
{
primes[a]++;
}
}
long long int res = 1;
for(auto p : primes) res = res * (p.second + 1) % mod;
cout << res << endl;
return 0;
}约数之和
题目描述：
给定 n个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。
输入格式：
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式:
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10^9+7 取模。
数据范围:
1≤ n ≤100
1≤ ai ≤2×10^9
输入样例：
3
2
6
8
输出样例：
252思路：
基于算术基本定理：
N = (p1^x1)(p2^x2)(p3^x3)…(pk^xk) 其中p为质因子
约数之和=（1+p1^1+p1^2……p1^x1)*……*（1+pk^1+pk^2……+pk^xk)
例如：
24=2 * 2 * 2 * 3=2^3 * 3
24的约数:1、2、3、4、6、8、12、24
约数之和=(1+2^1+2^2+2^3)*(1+3^1)=60=1+2+3+4+6+8+12+24
1.先求出并存好各质因子的指数
for(int i=2;i<=a/i;i++)
{
while(a%i==0)
{
a /= i;
primes[i]++;
}
}
if(a!=1)
{
primes[a]++;
}2.用公式求得约数之和
long long int res = 1;
for(auto p : primes)
{
long long a = p.first, b = p.second;
long long t = 1;
while (b--) t = (t * a + 1) % mod;
res = res * t % mod;
}解题代码：
# include <iostream>
# include <unordered_map>
using namespace std;
const int mod= 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int>primes;
while(n--)
{
int a;
cin >> a;
for(int i=2;i<=a/i;i++)
{
while(a%i==0)
{
a /= i;
primes[i]++;
}
}
if(a!=1)
{
primes[a]++;
}
}
long long int res = 1;
for(auto p : primes)
{
long long a = p.first, b = p.second;
long long t = 1;
while (b--) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}最大公约数
题目描述：
给定 n 对正整数 ai,bi 请你求出每对数的最大公约数。
输入格式：
第一行包含整数 n。
接下来 n 行，每行包含一个整数对 ai,bi。
输出格式：
输出共 n 行，每行输出一个整数对的最大公约数。
数据范围：
1≤n≤100000
1≤ai,bi≤2×1000000000
输入样例：
2
3 6
4 6
输出样例：
3
2解题代码：
辗转相除法：
# include <iostream>
using namespace std;
int gcd(int a,int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n;
cin >> n;
while(n--)
{
int a, b;
cin >> a >> b;
int res=gcd(a, b);
cout << res<<endl;
}
return 0;
}关于 a与b的公约数等于a与a%b的公约数的证明：
—设x是a与b的公约数，则x也是a-b的公约数；
—a%b=a-(a/b)*b，此处 a/b 为整除，令 a/b=c ，则 a%b=a-c*b，x是 a-c*b 的约数，即也是 a%b 的约数。
—设y是a%b的约数，则y也是a-c*b+c*b的约数，即y也是a的约数。
—综上所述， a与b的公约数等于a与a%b的公约数
图示：