概覽

• 大整數運算
• 分數運算
• 素數的獲取
• 因式分解
• 進制轉換

---

?

1、大整數運算（例題：1023 Have Fun with Numbers，1024 Palindromic Number）

在了解大整數之前，得先了解一下整型數據的范圍。（詳細請參考這里）

long int?就是int? 32位 long long int? ? ? 64位? ? ?注意，如果需要用到INT_MAX或LLONG_MAX之類的值的話，添加頭文件<limits.h> #include <stdio.h> #include <limits.h> int main() { printf("INT_MIN = %+d\n", INT_MIN);printf("INT_MAX = %+d\n", INT_MAX);printf("UINT_MAX = %u\n", UINT_MAX);printf("\n");printf("LONG_MIN = %+ld\n", LONG_MIN);printf("LONG_MAX = %+ld\n", LONG_MAX);printf("ULONG_MAX = %lu\n", ULONG_MAX);printf("\n");printf("LLONG_MIN = %+lld\n", LLONG_MIN);printf("LLONG_MAX = %+lld\n", LLONG_MAX);printf("ULLONG_MAX = %llu\n", ULLONG_MAX);printf("\n");
　　 return 0; }//輸出 INT_MIN = -2147483648 //即0x80000000 INT_MAX = +2147483647 //即0x7fffffff UINT_MAX = 4294967295LONG_MIN = -2147483648 LONG_MAX = +2147483647 ULONG_MAX = 4294967295LLONG_MIN = -9223372036854775808 //-LLONG_MAX-1 LLONG_MAX = +9223372036854775807 //0x7fffffffffffffff ULLONG_MAX = 18446744073709551615

大整數的定義，大整數也稱高精度整型數，就是位數太多，int或者long long都表示不了了。

struct BigN{int d[100];int len;//表示數的位數 BigN(){memset(d,0,sizeof(d));len=0;} }; 其中d[]存放各個位數，len存放長度。如n = 12345，用BigN可以表示成struct BigN a，其中a.d[0]=5，a.d[1]=4, a.d[2]=3, a.d[3]=2, a.d[4]=1; a.len=5。需要注意的是，原整數的高位存儲在數組的高位，原整數的低位存儲在數組的低位。這么存是為了計算加減的時候更方便，因為遍歷數組習慣上從0開始，而運算的時候也是從低位開始。 關于大整數的題，輸入的時候一般用字符串的形式，首先，將str[]轉化為BigN。 BigN change(char str[]) {BigN a;int len=strlen(str);for(int i=len-1;i>=0;i--)//個位存在a.d[0],十位存在a.d[1]...a.d[a.len++]=str[i]-'0';return a; }

大整數與大整數相加

BigN add(BigN a,BigN b) {BigN c;int carry=0;//進位for(int i=0;i<a.len||i<b.len;i++){int temp=carry+a.d[i]+b.d[i];c.d[c.len++]=temp%10;carry=temp/10;}//最高位還有進位的情況，如999+1=1,000if(carry>0)c.d[c.len++]=carry;return c; }

大整數與大整數相減（注：比如a-b，這里要求a>0,b>0且a>b，所以在相減之前要先判斷一下）

//此處保證a,b都是正的,且a>b BigN sub(BigN a,BigN b) {BigN c;for(int i=0;i<a.len;i++){if(a.d[i]<b.d[i]){//需要向高位借位a.d[i]+=10;a.d[i+1]--;//高位減1 }c.d[c.len++]=a.d[i]-b.d[i];}while(c.len>1 && c.d[c.len-1]==0)//刪除可能存在的前導0c.len--;return c; }

大整數與int型整數相乘（注：認為兩者都是正的！所以在相乘前先判斷一下）

BigN multiply(BigN a,int k) {BigN c;int carry=0;for(int i=0;i<a.len;i++){int temp=a.d[i]*k;c.d[c.len++]=temp%10;carry=temp/10;}//這里carry可能不止一位while(carry>0){c.d[c.len++]=carry%10;carry=carry/10;}return c; }

大整數與int型整數相除（注：認為兩者都是正的！所以在相除前先判斷一下）相除似乎從來沒考到過，自己也不熟悉，需引起注意！

//remainder為余數,傳入時為0 BigN divide(BigN a,int k,int &remainder) {BigN c;c.len=a.len;//注意，先賦值for(int i=a.len-1;i>=0;i--){remainder=remainder*10+a.d[i];c.d[i]=remainder/k;remainder=remainder%k;}//除去高位可能存在的前導0while(c.len>1 && c.d[c.len-1]==0)c.len--;return c; }

?

2、分數運算（例題：1088 Rational Arithmetic）

?對于分數的表示，可以定義一個結構體，分別表示分子和分母。

typedef long long LL; struct Fraction{LL up;//分子LL down;//分母 }; 需要注意的是，由于在運算過程中，如兩個int型相乘，可能會超過int的表示范圍，因此最好全都定義成long long型。 這里給分數制定三個規約—— 1、如果分母是負數，則把符號轉移到分子上； 2、如果分子是0，則把分母變成1； 3、要求分子和分母都是最簡的，即其最大公約數僅為1。 分數的化簡。特別注意：求分子分母的最大公約數需要加絕對值！錯好多次了！ //求最大公約數 int gcd(LL a,LL b){if(b==0) return a;else return gcd(b,a%b); } //分數化簡 void simplify(Fraction& a){if(a.down<0) {a.down = -a.down;a.up = -a.up;}if(a.up==0){a.down=1;}else{int commonFractor=gcd(abs(a.up), abs(a.down));//注意要加絕對值！！！a.up/=commonFractor;a.down/=commonFractor;} }

?

分數的輸出 一般來說，如果分母為1，則忽略，直接輸出分子部分，這個看題目要求。如果分子的絕對值比分母的絕對值要大，且題目有要求以真分數的形式輸出，則以語句2的形式；否則，以語句3的形式。 void printFraction(Fraction a){simplify(a);//打印前記得把分數化成最簡的形式if(a.down==1) printf("%lld",a.up);//如果分母為1，則只打印分子即可else{if(abs(a.up)>abs(a.down))//語句2printf("%lld %lld/%lld",a.up/a.down,abs(a.up)%a.down,a.down);elseprintf("%lld/%lld",a.up,a.down);//語句3} }

四則運算

//分數相加 Fraction add(Fraction a,Fraction b){Fraction c;c.down=a.down*b.down;c.up=a.up*b.down+a.down*b.up;simplify(c);return c; } //分數相減 Fraction sub(Fraction a,Fraction b){Fraction c;c.down=a.down*b.down;c.up=a.up*b.down-a.down*b.up;simplify(c);return c; } //分數相乘 Fraction multiply(Fraction a,Fraction b){Fraction c;c.down=a.down*b.down;c.up=a.up*b.up;simplify(c);return c; } //分數相除 Fraction divide(Fraction a,Fraction b){Fraction c;c.down=a.down*b.up;c.up=a.up*b.down;simplify(c);return c; }

?

3、素數的獲取

（1）暴力法（時間復雜度O(N√N)）這種方法比較常規，在N<10^5的數據是可行的，刷PAT好像已經夠用了。

//判斷素數 bool isPrime(int n) {if(n<=1) return false;int sqr=(int)sqrt(n);for(int i=2;i<=sqr;i++)if(n%i==0) return false;return true; } //逐個枚舉，獲取素數表 void getPrime() {for(int i=2;i<=46341;i++)if(isPrime(i) prime.push_back(i); }

（2）篩法（時間復雜度O(NloglogN)）

篩法的關鍵在于“篩”。用一個例子來說明：假設獲取1~15的素數

2 3 4 5 6 7 8 9 10 11 12 13 14 15 初始情況，假設所有數都是素數

1)首先需要明確2是素數，那么2的倍數全排除掉，即4 6 8 10 12 14 不是素數

2)遍歷到3，發現3沒有被篩掉，故3是素數，那么把3的倍數全排除掉，即6 9 12 15不是素數

3)遍歷到4，在前面的步驟中已經被排除了，明確它不是素數

...

以此類推，到最后剩下來的就是素數了。

const int maxn=16; vector<int> prime; bool isPrime[maxn]; //獲取15以內的所有素數 void getPrime() {memset(isPrime,true,sizeof(isPrime));for(int i=2;i<maxn;i++){//注意不能是<=，因為有效下標是0~maxn-1if(isPrime[i]){//如果當前這個數是素數 prime.push_back(i);//排除掉所有i的倍數for(int j=2*i;j<maxn;j+=i)isPrime[j]=false;}} }

4、質因子分解（直接見例題：1059 Prime Factors）

5、進制轉換

假設有這樣一個問題，有一個8進制的數a=646，我想轉化成16進制的數b，請問b是多少？（這道題我自己編的，我覺得完全可以出一道PAT20分的題啊）

#include <iostream> #include <string> #include <vector> #include <map> using namespace std;map<char,int> char_to_int; map<int,char> int_to_char;void init() {for(char ch='0';ch<='9';ch++){char_to_int[ch]=ch-'0';int_to_char[ch-'0']=ch;}int d=10;for(char ch='A';ch<='F';ch++){char_to_int[ch]=d;int_to_char[d]=ch;d++;} }//把進制base1的數str轉化為base2的數 string change(const string& str,int base1,int base2) {//首先，將進制為base1的數轉化為10進制的數int number_base10=0,product=1;int i=str.size()-1;while(i>=0){number_base10+=char_to_int[str[i]]*product;product*=base1;i--;}cout<<"base10: "<<number_base10<<'\n';//然后，把十進制的數轉化為base2進制的數string ans;do{int temp=number_base10 % base2;ans=string(1,int_to_char[temp])+ans;number_base10 /= base2;//注意，是除以base2,而不是10！}while(number_base10!=0);return ans; }int main() {init();string str_base8="646";//8進制的數646，對應的十進制數是422,16進制數是1A6string ans=change(str_base8,8,16);//把一個8進制的數轉化成16進制的數cout<<ans<<'\n';//輸出1A6string str_base16="1A6";ans=change(str_base16,16,8);cout<<ans<<'\n';//輸出646return 0; }

?

?

?

轉載于:https://www.cnblogs.com/kkmjy/p/9531966.html

總結

以上是生活随笔為你收集整理的基础数学问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。