进制转换
不用字符串模拟的情况
#include<iostream> #include<cstdio> #include<vector> using namespace std; int main(){ unsigned int n; while (cin>>n) { vector<int> arr; while(n){ arr.push_back(n%2); n/=2; } for(int i=arr.size()-1;i>=0;i--){ cout<<arr[i]; } cout<<endl; } return 0; }
核心:
- 首先取余数,然后整除2
- vector存储,之后逆序输出,但是如果用栈不用了
下面是用栈解决的情况:
#include <iostream> #include<stack> using namespace std; int main(){ unsigned int num; stack<int> s; while(cin>>num){ while(num){ s.push(num%2); num/=2; } while(!s.empty()){ cout<<s.top(); s.pop(); //因为这里有pop,所以可以将stack在循环外定义,不用针对每个二进制数建立一个stack } cout<<endl; } }
需要用字符串模拟的情况
在很多时候题目暗示了数字会很大(30位),在这种情况下用整型就无法表示了。一些基本数据类型的范围如下:
例题
进制转换
来源:牛客网
将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。
输入描述:
多组数据,每行为一个长度不超过30位的十进制非负整数。
(注意是10进制数字的个数可能有30个,而非30bits的整数)
输出描述:
每行输出对应的二进制数。
//这个数据会太长,所以需要用字符串模拟 #include <iostream> #include<string> #include<vector> using namespace std; //需要重写除法 string Div(string a ,int x){ int remain=0; for(int i=0;i<a.size();i++){ int current=remain*10+a[i]-'0';//余数*10+后一位除以x即可 a[i]=current/x+'0';//保存形式是字符,所以应该加‘0’ remain=current%x; } int pos=0; while(a[pos]=='0') pos++; return a.substr(pos);//去除前置多余的0 } int main(){ string str; while(cin>>str){ vector<int> ve; while(str.size()!=0){ ve.push_back((*(str.end()-1)-'0')%2); //ve.push_back(str[str.size()-1]-'0')%2); str=Div(str, 2); } for(int i=ve.size()-1;i>=0;i--) cout<<ve[i]; cout<<endl; } return 0; }
字符串除法模版
string Div(string a ,int x){ int remain=0; for(int i=0;i<a.size();i++){ int current=remain*10+a[i]-'0';//余数*10+后一位除以x即可 a[i]=current/x+'0';//保存形式是字符,所以应该加‘0’ remain=current%x; } int pos=0; while(a[pos]=='0') pos++; return a.substr(pos);//去除前置多余的0 }
记忆点⚠️:
- 需要一个余数变量remain和一个当前的被除数变量current
- 遍历字符串
- cur=re*10+a[i]-'0';a[i]=cur/x+'0';remain=current%x;
- 使用一个数组就行了,不必开辟新的数组
- 需要将前置的多余的0去掉(substr)
字符串乘法模版
string Multiple(string str,int x){ int carry=0; for(int i=str.size()-1;i>-1;i--){ int cur=x*(str[i]-'0')+carry; str[i]=cur%10+'0'; carry=cur/10; } if(carry) str="1"+str; return str; }
字符串加法模版
string Add(string str,int x){ int carry=x; for(int i=str.size()-1;i>-1;i--){ int cur=(str[i]-'0')+carry; str[i]=cur%10+'0'; carry=cur/10; } if(carry) str="1"+str; return str; }
⚠️记忆点:
- 进位carry和当前cur
- cur=x*(str[i]-'0')+carry.算str[i],算carry
- cur=str[i]-'0'+carry.算str[i],算carry
最大公因数/公倍数模版
//递归版 int GCD(int a,int b){ if(!b) return a; else return GCD(b, a%b); } //非递归版 int gcd(int a,int b) { if(!b) return a; int c; while(b) { c=b; b=a%b; a=c; } } //lcm int LCM(int a,int b){ return b/gcd(a,b)*a; //先除后乘,以免a*b溢出 }
素数
素数的判断分为筛法和非筛法,其中筛法更加重要和常用。
非筛法
非筛法针对于判断某个数是否是素数,只需要在[2,bound]内判断是否可以整除就行,但是很明显sqrt()函数是一个计算起来比较困难的函数,不应该在for循环中使用这个函数,应该提前定义一个变量将其计算出来。
筛法
如果要判断某个范围内有多少素数,那么用暴力遍历的方法就不好了(时间复杂度太大),必须用筛法解决。
//素数筛法 #include <iostream> #include <cstdio> #include<vector> using namespace std; const int MAXN=10001; vector<int> prime; bool isPrime[MAXN]; void Initial(){ for(int i=0;i<MAXN;i++){ isPrime[i]=true; } //全部初始化为true,即首先默认全是素数 isPrime[0]=false; isPrime[1]=false; for(int i=2;i<MAXN;i++){ if(!isPrime[i]) continue; //如果是素数,就推入向量 prime.push_back(i); //从i^2开始之后i的倍数都是素数,i到i*i之间不必算(i*k(k<i))已经被k的倍数计算过了,可以理解成某种剪枝 for(int j=i*i;j<MAXN;j+=i) isPrime[j]=false; } return; }
注意点⚠️:
- prime向量存储素数;isPrime数组判断是不是素数
- 数组初始化全部是true,isPrime[0]=false; isPrime[1]=false;
- 从2到MAXN,如果isPrime为假就跳过;如果为真就将i放入向量中并从i*i开始的每个倍数都将isPrime设置为真
快速幂
LL qpow(LL a, LL b, LL MOD) {//a 的 n 次方(可取模) LL ans = 1; while (b) { if (b & 1) { //若当前位是1 ans *= a; ans %= MOD; } b >>= 1; //byouyiyiwei a *= a; a %= MOD; } return ans; }
总体思想就是:每次都要将a平方,然后根据b当前位数上是否为1来决定需不需要在这个位置上累乘