约数个数,约数之和

未央吖

于 2023-03-22 23:59:01 发布

阅读量38

点赞数

分类专栏： 2023蓝桥杯文章标签： servlet

本文链接： https://blog.csdn.net/weixin_58183566/article/details/129720248

版权

2023蓝桥杯专栏收录该内容

8 篇文章 1 订阅

订阅专栏

约数个数

ans = (a1 + 1) * (a2 + 1) * (a3 + 1) …… *(an + 1);

求一个数（n）的约数个数

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
int a[N];

int main() {
	ll n, sum = 1;cin>>n;
	for (int i = 2; i <= n / i; i++) {
		ll sum1 = 0;
		while(n % i == 0) {
			n /= i;
			sum1++;
		}
		sum = sum * (sum1 + 1);
	}
	if (n > 1) sum *= 2;
	cout << sum; 
	return 0;
}

870. 约数个数 - AcWing题库

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
typedef long long ll;
#define x first
#define y second
const int N = 10000010;
const int mod = 1000000000 + 7;
int a[N];

int main() {
    unordered_map<int,int> q;
	int n; cin>>n;
	while(n--) {
		int m;cin>>m;
		for (int i = 2; i <= m / i; i++) {
			while(m % i == 0) {
				m /= i;
				q[i]++;
			}
		}
		if(m > 1) q[m]++;
	}	
	ll sum = 1;
	for (auto it = q.begin(); it != q.end(); it++) {
		if(it->second) sum = sum *(it->second + 1) % mod;
	}
	cout << sum;
	return 0;
}

约数之和

871. 约数之和 - AcWing题库

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1000000000 + 7;
unordered_map<int,int> q;

int main() {
	int n; cin>>n;
	while(n--) {
		int m;cin>>m;
		for (int i = 2; i <= m / i; i++) {
			while(m % i == 0) {
				m /= i;
				q[i]++;
			}
		}
		if(m > 1) q[m]++;
	}
	
	ll sum = 1;
	for (auto it = q.begin(); it != q.end(); it++) {
		int a = it->first, b = it->second;
		ll sum1 = 1, t = 1;
		while(b--) {
		    t = (t * a) % mod;
		    sum1 = (sum1 + t) % mod;
		}
		sum = (sum * sum1) % mod;
	}
	cout << sum  % mod;
	return 0;
}