今天讲数论
1.进制问题（将n转换成k进制数）：
1.方法：短除法
将n/k，保存，将商当做新的n，将余数保存，直到商为0，将余数（包括0），倒序输出，即得n的k进制数
2.关于高精四则运算（我本以为不用怎么整的）：
举个加和乘的例子...
众所周知，a+b problem是最简单的红题，再加个*也无伤大雅，代码如下（没文件头）：
int main(){
int a,b;
cin>>a>>b;
cout<<a*b;
return ;
}
直到你加了这些东西：
#include<bits/stdc++.h>
using namespace std;
struct nu{
int a[];
int l;
nu(){
l=;
memset(a,,sizeof(a));
}
friend istream& operator>>(istream &cin,nu &x){ //意思是:重载>>（用于cin，读到x里面）
static char s[];
cin>>s;
int l=strlen(s);
for(int i=;i<=l;i++)
x.a[i]=s[l-i-]-'';
x.l=l;
return cin;
}
friend ostream& operator<<(ostream &cout,const nu &x){ //与上面大同，多了个const，在于使x值在输出前后值相同
for(int i=x.l-;i>=;i--)
cout<<x.a[i];
}
};
nu operator+(const nu &x,const nu &y){ //重载+
nu ans;
int len=max(x.l,y.l);
for(int i=;i<len;i++)
ans.a[i]+=x.a[i]+y.a[i];
for(int i=;i<len;i++){
if(ans.a[i]>=){
int now=ans.a[i]/;
ans.a[i+]+=now;
ans.a[i]%=;
}
while(ans.a[len+]) len++;
}
ans.l=len;
return ans;
}
nu operator*(const nu &x,const nu &y){ //重载*用了非常简单而经典的高精算法
nu ans;
for(int i=;i<x.l;i++)
for(int j=;j<y.l;j++)
ans.a[i+j]+=x.a[i]*y.a[j];
ans.l=x.l+y.l;
for(int i=;i<ans.l;i++){
ans.a[i+]+=ans.a[i]/;
ans.a[i]%=;
}
while(ans.l>&&!(ans.a[ans.l]))
ans.l--;
ans.l++;
return ans;
}
int main(){
nu a,b;
cin>>a>>b;
cout<<a*b;
return ;
}
6-9行是构造函数，用于memset
10-22是重载cin与cout，背过就好
加const的原因是进行运算的值由符号返回，而从不是变量本身，所以没有赋值的话不能改变变量的值，也更方便电脑理解，可以看到stl里面好多函数用了const
至于&符号，用因如下：
每次用函数运算时，每个函数形如 f(int n)，都要把用的变量“n”的值拷贝一份进行运算，如果引用数组就更慢，还更占内存，用了&符号意在免去拷贝操作，直接引用其值，
（反正有了const不用怕数值变化）这就算一个优化
后面一直到主函数之前都是重载运算符
3.关于素数（又是各种筛法）
粘下模板：
1.埃氏筛：
#include<bits/stdc++.h>
using namespace std;
bool no[]={,};
int pri[];
int tot;
inline void p(int t){
for(int i=;i<=t;i++)
if(!no[i]){
pri[++tot]=i;
for(int j=i+i;j<=t;j+=i)
no[j]=;
}
}
int n;
int main(){
scanf("%d",&n);
p(n);
for(int i=;i<=tot;i++)printf("%d\n",pri[i]);
return ;
}
欧拉筛（线性筛）：
#include<bits/stdc++.h>
using namespace std;
bool no[];
int pri[];
int tot;
int n;
inline void p(int n){
for(int i=;i<=n;i++){
if(!no[i])
pri[++tot]=i;
for(int j=;j<=n&&i*pri[j]<=n;j++){
no[i*pri[j]]=;
if(!(i%pri[j])) break;
}
}
}
int main(){
scanf("%d",&n);
p(n);
for(int i=;i<=tot;i++)printf("%d\n",pri[i]);
return ;
}
3.exgcd：
#include<bits/stdc++.h>
using namespace std;
int a,b,x,y;
inline int exgcd(int a,int b,int &x,int &y){ //利用性质gcd（a,b）=gcd（b,a%b）
if(!b){
x=;
y=;
return a;
}int g=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=(t-(a/b)*x);
return g;
}
int main(){
cin>>a>>b;
exgcd(a,b,x,y);
if(x<) x+=b;
cout<<x;
return ;
}
练多了不解释...
下午考试了..我..应该..大概不会爆零