UVa294 - Divisors (數論 Math theorm)

題目大意：

給你一段數字，求出範圍數字內可以被最多數字整除於 0。(如果有一樣，輸出最小)
並透過格式輸出

分析：

這裡有一個地方我覺得很酷，就是

6 的除數有 1 2 4 6 總共為 4
6 = 2^1 * 3^1
=> 2 * 2 => 4

一開始覺得很神奇，但後來想通了也沒什麼，但想出方法的真的很強呢。

Hint:
x ^ 0 = 1，能明白固中道理，這題目就簡單了。

教會我的blog

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define Maxn_Num 1000000000
using namespace std;
enum {Maxn = Maxn_Num , sqrt_max = (int)sqrt(Maxn_Num)};
vector<int> prime ;

int count_div(int x ){
    int total =1 , j ;
    for(int i = 0 ; i < prime.size() && x ; i++){
        j = 1 ;
        while(x % prime[i] ==0 ){
            x /= prime[i];
            j++ ;
        }
        total *= j ;
    }
    return total;
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin) ;
#endif // LOCAL

    int flag ;
    for(int i = 2 ; i <= sqrt_max ; i++){
        flag = 1 ;
        for(int j = 2 ; j <= sqrt(i) ; j++ ){
            if(i % j == 0 ){
                flag = 0;
                break;
            }
        }
        if(flag)
            prime.push_back(i);
    }

/**<      //debug
    for(auto it : prime)
        cout << it << '\n' ;
*/
    int n , l , u, temp;
    cin >> n ;
    while(n--){
        cin >> l >> u ;
        pair<int , int> divMax = {0,0} ;
        for(int i = l ; i <= u ; i++){
            temp = count_div(i);
            if ( temp > divMax.second){
                divMax.first = i ;
                divMax.second = temp ;
            }
        }
        cout << "Between " << l << " and " << u << ", " << divMax.first << " has a maximum of " << divMax.second << " divisors.\n";
    }

    return 0;
}