UVA 294 - Divisors
补题
一道简单的数论公式题
题意:
给定一个区间, 求在这个区间[L, R]中因子最多的数, 并输出它和它的因子个数.
题解:
初见杀...
这道题用到了 算术基本定理(又称为正整数唯一分解定理) , 即对于一个大于1的自然数, 如果自身不是质数, 那么一定可以写为两个以上质数的积, 且从小到大排列后有唯一写法.
所以对于区间[L, R]中的所有数进行分解, 得到唯一表达式, 之后计算因子个数.
首先对于12, 总共有6个因子(1, 12, 2, 6, 3, 4), 它的唯一表达式是: 12 = 2 ^ 2 * 3 ^ 1.
对于24, 总共有8个因子(1, 24, 2, 12, 3, 8, 4, 6), 它的唯一表达式是: 24 = 2 ^ 3 * 3 ^ 1.
我们可以看出来规律, 将其唯一表达式出现的所有质因子的指数加上1, 之后取积, 就是其因子个数.
因子个数 = 所有质因子的指数 + 1 的积.
通过质数筛来加速运算.
Accept G++ 530ms:
/**
* @author Moe_Sakiya sakiya@tun.moe
* @date 2018-11-26 18:59:49
*
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int maxN = 50005;
long long int arrPrime[maxN];
bool isPrime[maxN];
int cnt;
void calPrimes() {
memset(isPrime, 1, sizeof(isPrime));
cnt = 0;
isPrime[1] = false;
for (long long int i = 2; i < maxN; i++) {
if (isPrime[i] == true)
arrPrime[cnt++] = i;
for (int j = 0; j < cnt && i * arrPrime[j] < maxN; j++) {
isPrime[i * arrPrime[j]] = false;
if (i % arrPrime[j] == false)
break;
}
}
return;
}
long long int calNum(int n) {
long long int ret = 1;
int num;
for (int i = 0; i < cnt; i++) {
if (n % arrPrime[i] == 0) {
num = 1;
while (n % arrPrime[i] == 0 && n > 0) {
num++;
n /= arrPrime[i];
}
ret *= num;
}
}
return ret;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
long long int maxNum, maxCount;
int t, l, r;
calPrimes();
scanf("%d", &t);
while (t--) {
maxNum = 0;
maxCount = 0;
scanf("%d %d", &l, &r);
for (int i = l; i <= r; i++) {
long long int tmp = calNum(i);
if (tmp > maxCount) {
maxCount = tmp;
maxNum = i;
}
}
printf("Between %d and %d, %lld has a maximum of %lld divisors.\n", l, r, maxNum, maxCount);
}
return 0;
}