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;
}