w22116972
3/28/2014 - 4:19 PM

UVA 10290

UVA 10290

#include <stdlib.h>
#include <iostream>
#include <vector>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <map>

#define MAX 1000005     // input max_value = 9*10^14
                        // sqrt(max_value) = 3*10^7
                        // 這題的這個測資不太理想,必須到1000005才不會LTE,這也是看網路上

using namespace std ;

bool is_prime[MAX];
vector<int> prime_number;

void setPrimeTable(){                   // 就基本的建質數表
    /*
    for (long long i=3; i<MAX; i+=2)
        is_prime[i]=true;
     */
    is_prime[0]=is_prime[1]=true;
    is_prime[2]=false;
    prime_number.push_back(2);
    for (int i=3; i<MAX; i+=2){
        if (!is_prime[i]){
            prime_number.push_back(i);
            for (int j=3; i*j<MAX; j+=2)
                is_prime[i*j]=true;
        }
    }
}

int main(int argc, const char * argv[]) // 這題所求為奇因數的個數
{
    setPrimeTable();
    long long n;
    while(cin >> n)
    {
        if (!n)                         // 如果輸入為0 則直接輸出1
            cout << 1 <<endl;
        else{
            while (n%2==0)              // 如果為偶數則不考慮 因此直接猛除即可
                n/=2;
            long long max=n;
            if (n==1){                  // 如果此時為1 則代表原來全為2的次方 直接輸出1不解釋
                cout << 1 <<endl;
                continue;
            }
            long long ans=1;
            for (long long i=1; i<prime_number.size() && prime_number[i]*prime_number[i]<=max; i++) {
                long long count=0;
                while (n%prime_number[i]==0) {      // 如果可整除,則先除掉使其變小
                    n/=prime_number[i];
                    count++;
                }
                ans*=(count+1);                     // 因為要考慮到 0次方的情形 所以要加1
                if (n==1)                           // 被除到0就可以跳出了 後面不需走完迴圈
                    break;
            }
            if (n!=1)                               // 如果不等於1 代表有更大的質數超越質數表
                ans*=2;
            cout << ans <<endl;
        }
        
    }
    return 0;
}