约数题型
求一个数的所有约数
约数个数
约数之和
求一个数的所有约数
869.试除法求约数
https://www.acwing.com/problem/content/description/871/
算法
一个数约数是一个数的因数,求x的约数就用想除以i(遍历)
for (int i = 2; i <= n; i ++ )
{
if (x % i == 0) cnt ++ ;//cnt记为约数个数
}
我们可以发现,约数是成对出现的。
例如:
当x = 12时,2和6,3和4;
即当d是x的约数时, n/d也一定是x的约数。
因此枚举时,可以枚举小的那个,大的那个直接算好加进去。
for (int i = 2; i <= n/i; i ++ )
{
if (x % i == 0)
{
cnt ++ ;
if (x / i != i) cnt ++ ;
}
}
C++ 代码 链接里面题目的代码(y总)
代码用了容器来储存所有约数,方便用于排序
#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个数,循环里n / i的时间复杂度是sqr(n)
排序的时间复杂度
n + n/2 + n/3 +.....n/n = n (1 + 1/2 + 1/3 +...1/n)
总共nlogn个约数
期望就是O(nlogn)
约数个数
约数个数问题的重点是如何表示d是N的约数
因此,d可以通过排列组合列出所有可能。
870.约数个数
https://www.acwing.com/problem/content/description/872/
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;//定义哈希表记录P^a的P和a
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;//p.secong是a的值。
cout << res << endl;
}
约数之和
871.约数个数
https://www.acwing.com/problem/content/description/873/
这个题的难点为:如何利用哈希表储存的底数和指数来表示约数之和。
操作代码表示为
int t = 1;
while (a -- ) t = (t * p + 1);
C++ 代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int 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;
while (b -- ) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}