Loading... 高精度算法 <!--more--> ----- * 大数的存储 * 思路大概就是把数以字符串的形式读入，然后将它们一位一位倒叙存进一个整形数组。 * 高精度加法 * 把每一位相加，若有进位就将下一位加一。 * 高精度乘法 与高精度加法类似。 * 示例代码 ```cpp #include<bits/stdc++.h> using namespace std; string s1,s2; int input(string &s,int a[],int &len){ cin>>s; len=s.length(); for(int i=0;i<len;i++){ a[i]=s[len-i-1]-'0'; } return len; } int plus_(int a[],int b[],int lena,int lenb,int c[]){//O(n) int lenc=0; while(lenc<lena||lenc<lenb){ c[lenc]=a[lenc]+b[lenc]; if(c[lenc]>=10){ c[lenc]-=10; c[lenc+1]++; } lenc++; } if(c[lenc]==0){ lenc--; } return lenc; } int time_(int a[],int b[],int lena,int lenb,int c[]){//O(n^2) int lenc; for(int i=0;i<lenb;i++){ for(int j=0;j<lena;j++){ c[i+j]+=a[j]*b[i]; lenc=i+j; } } lenc+=20; for(int i=0;i<2000;i++){ c[i+1]+=c[i]/10; c[i]%=10; } while(c[lenc]==0){ lenc--; } return lenc; } int main(){ int a[2000],lena,b[2000],lenb,c[2000],lenc; memset(a,0,sizeof(a)); memset(b,0,sizeof(a)); memset(c,0,sizeof(a)); input(s1,a,lena); input(s2,b,lenb); lenc=time_(a,b,lena,lenb,c); for(int i=lenc;i>=0;i--){ cout<<c[i]; } cout<<endl; memset(c,0,sizeof(c)); lenc=plus_(a,b,lena,lenb,c); for(int i=lenc;i>=0;i--){ cout<<c[i]; } } ``` 快速幂 --- * $a^bmodc;a,b,c\\le 10^9$ * 代码见Day1 进制转换 ---- * 从10进制转其他进制 * 代码： ```cpp #include<bits/stdc++.h> using namespace std; char s[100]; int tot; int main(){ int a[20000]; int b=121; int tobase=2; cin>>b>>tobase; while(b>0){ a[tot++]=b%tobase; b/=tobase; } for(int i=tot-1;i>=0;i--){ printf("%d",a[i]); } return 0; } ``` * 从其它进制转10进制 * 代码： ```cpp #include<bits/stdc++.h> using namespace std; char s[100]; int main(){ int base; cin>>base; scanf("%s",s); int x=1; int num=0; int l=strlen(s); for(int i=l-1;i>=0;i--){ int a = s[i]-'0'; if(a>=base){ cout<<"Error!"; return 0; } num += a*x; x *= base; } cout<<num; return 0; } ``` 素数 -- * 大于一且因数只有1和它本身。 * 算数基本定理 * 任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积$N=P\_1^{a\_1}\\times P\_2^{a\_2}\\times P\_3^{a\_3}\\times ......\\times P\_n^{a\_n}$，这里$P\_1<P\_2<P\_3......<P\_n$均为质数，其中指数$a_i$是正整数。 * 判断一个数是不是素数 * 一般算法 `cpp #include<bits/stdc++.h> using namespace std; bool is_prime(int x){ for(int i=2;i*i<=x;i++){ if(x%i==0) return 0; } return 1; } int main(){ int n; cin>>n; cout<<is_prime(i); return 0; }` * $O(nloglogn)$算法 `cpp #include<bits/stdc++.h> using namespace std; bool a[100000005]; int x[100000005]; int find_prime(int n){ int tot=0; for(int i=2;i<=n;i++){ if(!a[i]){ x[tot++]=i; for(int j=2;j*i<=n;j++){ a[j*i]=1; } } } return tot; } int main(){ int len=find_prime(100000); for(int i=0;i<len;i++){ cout<<x[i]<<" "; } return 0; }` gcd/lcm ------- * gcd:最大公约数 * lcm:最小公倍数 * $(a,b)\[a,b\]=ab$ ### gcd * $gcd(a,b)=p\_1^{min(a\_1,b\_1)}\\times p\_2^{min(a\_2,b\_2)}\\times ...\\times p\_n^{min(a\_n,b_n)}$ * 怎么算？ * 辗转相减 $gcd(a,b) = gcd(b,a-b)$ * 辗转相除法 $gcd(a,b) = gcd(b,a\\%b)$ * 代码如下： `cpp int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }` ### lcm * $lcm(a,b)=p\_1^{max(a\_1,b\_1)}\\times p\_2^{max(a\_2,b\_2)}\\times ...\\times p\_n^{max(a\_n,b_n)}$ * 代码如下： `cpp int lcm(int a,int b){ return a*b/gcd(a,b); }` #### 示例代码 ```cpp #include<bits/stdc++.h> using namespace std; int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); } int lcm(int a,int b){ return a*b/gcd(a,b); } int main(){ cout<<gcd(3,4)<<endl; cout<<lcm(3,4); return 0; } ``` 裴蜀定理 ---- * $gcd(a,b)=d\\Rightarrow ax+by=d$ * $gcd(a,b)=1\\Leftarrow\\Rightarrow ax+by=1$ Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏