求約數 hdu2601 An easy problem

這題有兩種方法，一種是直接sqrt(n)的複雜度求約數數量

還有一種當然是比較快的方法，通過質因數分解求約數數量

為什麼是求約數數量呢

可以發現 n+1=(i+1)*(j+1)

 是以我們隻需要求出約數的數量，就能知道i+1有多少種情況了，然後還需要讨論一下

假如n是12，約數有1,2,3,4,6,12

那麼，因為是偶數個約數，是以總是兩兩配對的，一共有3對，是以i+1可能為1,2,3

又因為i不能為0，是以i+1不能為1，是以對數還要減小一對

是以如果約數個數為n,n為偶數，答案就等于n/2-1

如果n等于16，約數有1,2,4,8,16

那麼，因為奇數個約數，是以中間一個沒法配對，但是可以發現，有(n+1)/2對，除去(1,16)這一對，還有(n+1)/2-1對

綜上所述，如果我們知道了約數的個數是n，那麼答案就是(n+1)/2-1

#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int prime[100000], vis[MX], rear = 0;
void init() {
    rear = 0;
    vis[1] = 1;
    for(int i = 2; i < MX; i++) {
        if(vis[i]) continue;
        prime[++rear] = i;

        if((LL)i * i >= MX) continue;
        for(int j = i * i; j < MX; j += i) {
            vis[j] = 1;
        }
    }
}

int main() {
    int T;
    init();
    scanf("%d", &T);
    while(T--) {
        LL n;
        scanf("%I64d", &n);
        n++;

        int ans = 1, s;
        for(int i = 1; (LL)prime[i]*prime[i] <= n; i++) {
            s = 0;
            while(n % prime[i] == 0) {
                s++;
                n /= prime[i];
            }
            ans *= s + 1;
            if(n == 1) break;
        }
        if(n != 1) ans *= 2;

        printf("%d\n", (ans + 1)/2 - 1);
    }
    return 0;
}