补题
一道简单的数论公式题

题意:
给定一个区间, 求在这个区间[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;
}