qbxt Day 1 morning 重点笔记
——2020.3.8 济南 主讲：钟皓曦
1
正数%负数==正数
负数%正数==负数
负数%负数==负数
a%b的答案的符号取决于a的符号。
2
快速幂：给定x,y,p，求x9
常规，(不够快)：
//O(i)算法，非快速幂
int ans=1;
for(int i=1;i<=y;i++){
ans=(long long)ans*x%p;
}
int ans=1;
for(int i=1；i<=y;i++){
ans=(1ll*ans)*x%p;
//1ll指long long下的1，可以将int ans转换为long long ans
}
int ans=1;
for(int i=1；i<=y;i++){
ans=(0ll+ans)*x%p;
}
//10^8可以在1s中运行完，而这种代码在最坏情况下为10^9
快速幂：
思想：大问题化小问题
\[x^n-->(x^(n/2))^2
\]
\]
//快速幂_递归
inline int quick_pow(int x,int y,int p){
if(y==0) return 1; //x^0==1
int ans=quick_pow(x,y>>1,p);
//y>>1==y/2;
ans=1ll*ans*ans%p;
if(y%2==1) z=1ll*ans*x%p;
return ans;
}
3
最大公因数，最小公倍数
gcd(a,b)：找到一个最大的g，使g|a,g|b。
lcm(a,b)：找到一个最小的l，使a|l,b|l。
\[gcd(a,b)*lcm(a,b)==a*b
\]
\]
4
高精度
数的存储：
struct Edge{
int n,z[2333];
//z[1]个位,z[2]十位，以此类推
//n表示有n位
Edge{
n=1;
memset(a,0,sizeof(z));
}
inline void init(){ //读入高精度整数
scanf("%s",s+1);
int len=strlen(s+1);
reverse(s+1,s+len+1); //把给定区间进行反转
n=len;
for(int i=1;i<=n;i++){
z[i]=s[i]-'0';
}
}
inline void print(){ //输出高精度整数
for(int i=n;i>=1;i--) printf("%d",z[i]);
}
};
计算a是否小于b
bool operator<(const Edge &a,const Edge &b){
//operater< 指重载小于运算符
//为了计算a是否小于b
if(a.n<b.n) return a.n<b.n;
for(int i=a.n;i>=1;i--){
if(a.z[i]!=b.z[i]) return a.z[i]<b.z[i];
}
return false;
}
计算a小于等于b
bool operator<=(const Edge &a,const Edge &b){
if(a.n<b.n) return a.n<b.n;
for(int i=a.n;i>=1;i--){
if(a.z[i]!=b.z[i]) return a.z[i]<b,z[i];
}
return true;
}
高精度加法
Edge operator+(const Edge &a,const Edge &b){
Edge c;
c.n=max(a.n,b.n);
for(int i=1;i<=c.n;i++) c.z[i]=a.z[i]+b.z[i];
for(int i=1;i<=c.n;i++){
c.z[i+1]+=c.z[i]/10;
c.z[i]=c.z[i]%10;
}
if(c.z[n+1]!=0) c.n++;
return c;
}
高精度乘法
Edge operator*(const Edge &a,const Edge &b){
Edge c;
c.n=a.n+b.n;
for(int i=1;i<=a.n;i++){
for(int j=1;j<=b.n;j++){
c.z[i+j-1]+=a.z[i]*b.z[j];
}
}
for(int i=1;i<=c.n;i++){
c.z[i+1]+=c.z[i]/10;
c.z[i]=c.z[i]%10;
}
while(c.n!=1&&c.z[c.n]==0) c.n--;
return c;
}
luogu:
1226,1143,1017