- caoshiyue's blog
c++手搓函数
- 2023-10-16 21:57:47 @
目录:
① 简单数学
②类型互换
③进制章
④高精度
⑤回文杂学(好像没什么用)
⑥火车头
以上就是本章的全部内容
欢迎随时提议
制作不易,还望珍惜一下别人的学习成果
声明一下:某些手搓函数可能可以被系统自带的函数代替,作者只是想分享一下手搓成果而已(不要刷屏讨论!!!)
重要的事情说三遍:
严禁刷屏 不喜勿喷
严禁刷屏 不喜勿喷
严禁刷屏 不喜勿喷
正文:
简单数学
素数
bool prime(int n){
if(n<=1) return false;
if(n==2) return true;
for(int i=2;i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}
埃氏筛法
void init(long long n){
for(int i=2;i<=sqrt(n);i++){
if(a[i]==0){
for(int j=i+i;j<=n;j+=i){
a[j]=1;
}
}
}
}
最大公因数
long long gcd(long long a,long long b){
return !b ? a : gcd(b,a%b);
}
最小公倍数
long long a,b;
cin>>a>>b;
long long x=gcd(a,b);
cout<<a*b/x<<endl;
快速幂
long long fpm(long long a,long long b,long long p){
long long ans=1;
while(b){
if(b&1){
ans=ans*a%p;
}
a=a*a%p;
b>>=1;
}
return ans;
}
类型互换
string转long long
long long str_long(string x){
long long a=0,len=x.size();
for(int i=0;i<len;i++) {a*=10,a+=int(x[i]-'0');}
return a;
}
long long转string
string long_str(long long x){
string a="";
while(x!=0) {a+=char(x%10+'0'),x/=10;}
return a;
}
进制章
n进制转10进制
long long fn_10(string m,long long n){
long long sum=0;
int len=m.length();
for(int i=0;i<len;i++){
if(m[i]<='9'){
sum=sum+(m[i]-'0')*pow(n,len-i-1);
}else{
sum=sum+(m[i]-'A'+10)*pow(n,len-i-1);
}
}
return sum;
}
10进制转n进制
long long f10_n(long long m,long long n){
string sum="";
while(m!=0){
int x=m%n;
if(x>=10){
char z=char((x-10)+'A');
sum+=z;
}else sum+=char(x+'0');
m=m/n;
}
long long ans=0;
for(int i=sum.size()-1;i>=0;i--){
ans*=10;
ans+=int(sum[i]-'0');
}
return ans;
}
高精度
高精度加法
string High_precision_addition(string a,string b){
int s1[251]={0},s2[251]={0},s3[251]={0},lena,lenb,lenc;
lena=a.size();
lenb=b.size();
lenc=max(lena,lenb)+1;
for(int i=0;i<lena;i++) {s1[i]=a[lena-1-i]-'0';}
for(int i=0;i<lenb;i++) {s2[i]=b[lenb-1-i]-'0';}
for(int i=0;i<=lenc;i++) {s3[i]+=s1[i]+s2[i],s3[i+1]=s3[i]/10,s3[i]%=10;}
while(s3[lenc]==0&&lenc>=1) lenc--;
string x="";
for(int i=lenc;i>=0;i--) x+=char(s3[i]+'0');
return x;
}
高精度减法
string High_precision_subtraction(string x2,string y2){
char a1[1001],b1[1001];
int lenx2=x2.size(),leny2=y2.size(),lena=x2,lenb=y2,lenc;
for(int i=0;i<lenx2;i++) a1[i]=x2[i];
for(int i=0;i<leny2;i++) b1[i]=y2[i];
int a[1001]={},b[1001]={},c[1001]={};
if(lena<lenb||lena==lenb&&strcmp(a1,b1)<0) {cout<<"-",swap(a1,b1);}
lena=strlen(a1),lenb=strlen(b1),lenc=lena;
for(int i=0;i<lena;i++) a[lena-i-1]=a1[i]-'0';
for(int i=0;i<lenb;i++) b[lenb-i-1]=b1[i]-'0';
for(int i=0;i<lenc;i++){
if(a[i]<b[i]) {a[i]+=10,a[i+1]--;}
c[i]=a[i]-b[i];
}
while(c[lenc-1]==0&&lenc>1) lenc--;
string x="";
for(int i=lenc-1;i>=0;i--) x+=char(c[i]+'0');
return x;
}
高精度减法(小数部分)
string xHigh_precision_addition(string a,string b){
int s1[251]={0},s2[251]={0},s3[251]={0},lena,lenb,lenc;
lena=a.size();
lenb=b.size();
lenc=max(lena,lenb)+1;
if(lenc==lena+1){
for(int i=1;i<=lena;i++) s1[i]=int(a[i-1]-'0');
for(int i=1;i<=(lenc-lenb-1);i++) b="0"+b;
lenb=b.size();
for(int i=1;i<=lenb;i++) s2[i]=int(b[i-1]-'0');
}else{
for(int i=1;i<=lenb;i++) s2[i]=int(b[i-1]-'0');
for(int i=1;i<=(lenc-lena-1);i++) a="0"+a;
lena=a.size();
for(int i=1;i<=lena;i++) s1[i]=int(a[i-1]-'0');
}
for(int i=lenc-1;i>=1;i--) {s3[i]+=s1[i]+s2[i],s3[i-1]=s3[i]/10,s3[i]%=10;}
string x="";
for(int i=0;i<lenc;i++) x+=char(s3[i]+'0');
return x;
}
高精度乘法
string High_precision_multiplication(string x2,string y2){
char a1[1001],b1[1001];
int a[1001]={},b[1001]={},c[1001]={};
int lenx2=x2.size(),leny2=y2.size(),lena=lenx2,lenb=leny2,lenc=lena+lenb;
for(int i=0;i<lenx2;i++) a1[i]=x2[i];
for(int i=0;i<leny2;i++) b1[i]=y2[i];
for(int i=0;i<lena;i++) a[lena-i-1]=a1[i]-'0';
for(int i=0;i<lenb;i++) b[lenb-i-1]=b1[i]-'0';
for(int i=0;i<lena;i++){
int x=0;
for(int j=0;j<lenb;j++) c[i+j]+=a[i]*b[j]+x,x=c[i+j]/10,c[i+j]%=10;
c[lenb+i]=x;
}
while(c[lenc-1]==0&&lenc>1) lenc--;
string x="";
for(int i=lenc-1;i>=0;i--) x+=char(c[i]+'0');
return x;
}
高精度除法(带余)
int a[501],b[501],c[501];
void init(int a[]){
string s;
cin>>s;
a[0]=s.length();
for(int i=1;i<=a[0];i++) a[i]=s[a[0]-i]-48;
}
void print(int a[]){
if(a[0]<=0) {cout<<0<<endl;return;}
for(int i=a[0];i>0;i--) cout<<a[i];
cout<<endl;
return;
}
int compare(int a[],int b[]){
if(a[0]>b[0]) return 1;
if(a[0]<b[0]) return -1;
for(int i=a[0];i>0;i--){
if(a[i]>b[i]) return 1;
if(a[i]<b[i]) return -1;
}
return 0;
}
void jian(int a[],int b[]){
int flag=compare(a,b);
if(flag==0) {a[0]=0;return;}
if(flag==1){
for(int i=1;i<=a[0];i++){
if(a[i]<b[i]) {a[i+1]--,a[i]+=10;}
a[i]-=b[i];
}
while(a[0]>0&&a[a[0]]==0) a[0]--;
return;
}
}
void High_precision_comparison(int p[],int q[],int det){
for(int i=1;i<=p[0];i++) q[i+det-1]=p[i];
q[0]=p[0]+det-1;
}
void High_precision_division(){
init(a);
init(b);
int tmp[501];
c[0]=a[0]-b[0]+1;
for(int i=c[0];i>0;i--){
memset(tmp,0,sizeof(tmp));
High_precision_comparison(b,tmp,i);
while(compare(a,tmp)>=0) {c[i]++,jian(a,tmp);}
}
while(c[0]>0&&c[c[0]]==0) c[0]--;
print(c);
print(a);
return;
}
只需要调用High_precision_division()就行了
回文杂学 (好像没什么用)
回文(正整数)
bool palindromic_number(int n) {
string s;
while (n != 0) {
s += (n % 10) + '0';
n /= 10;
}
int len = s.size();
for (int i = 0; i < len/2; i++) {
if (s[i] != s[len - 1 - i]) {
return false;
}
}
return true;
}
回文string字串
bool palindromic_string(string s){
int len = s.size();
for (int i = 0; i < len/2; i++) {
if (s[i] != s[len - 1 - i]) {
return false;
}
}
return true;
}
回文char字串
bool palindromic_char(char s[]){
int len = strlen(s);
for (int i = 0; i < len/2; i++) {
if (s[i] != s[len - 1 - i]) {
return false;
}
}
return true;
}
火车头
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")