C++中約數(shù)定理的實例詳解
對于一個大于1正整數(shù)n可以分解質(zhì)因數(shù):n = p1^a1*p2^a2*......pk^ak,則n的正約數(shù)的個數(shù)就是  :(a1+1)*(a2+1)*......*(ak+1)
其中a1、a2、a3…ak是p1、p2、p3,…pk的指數(shù)。
用這個定理求一個數(shù)的約數(shù)個數(shù)是非常快的,貼出一道訓(xùn)練題目:
hdu 1492 -求約數(shù)的個數(shù)
貼出代碼:
//約數(shù)定理的 #include <iostream> #include <algorithm> #include <iterator> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <vector> #include <queue> #include <set> using namespace std;  #define ll long long  int main() {   // freopen("s.cpp","r",stdin);    ll n;   while(scanf("%lld",&n) != EOF)   {     if(!n) break;      ll sum = 1;     /* x = p1^a1*p2^a2*p3^a3...pk^ak     yueshu = (a1+1)*(a2+1)*...*(ak+1)*/     for(ll i = 2; i*i <= n; i++){       int cou = 0;       if(n%i==0){         cou = 1;         n /= i;         while(n%i==0){           cou++;           n /= i;         }       }       if(cou != 0){         sum = sum*(cou+1);       }     }     if(n != 1){       sum = sum*2;     }     if(sum==1 && n==1){       sum = 1;     }     printf("%lld/n",sum);   }   return 0; } 感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
新聞熱點
疑難解答