清北学堂—2020.3NOIP数学精讲营—Day 1 morning 重点笔记

qbxt Day 1 morning 重点笔记

——2020.3.8 济南主讲：钟皓曦

1

正数%负数==正数

负数%正数==负数

负数%负数==负数

a%b的答案的符号取决于a的符号。

2

快速幂：给定x,y,p，求x^{y%p,0<=x,y,p<=10}9

常规，(不够快)：

//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

巴特西

清北学堂—2020.3NOIP数学精讲营—Day 1 morning 重点笔记

qbxt Day 1 morning 重点笔记

——2020.3.8 济南主讲：钟皓曦

1

2

3

4

最新文章

热门文章

巴特西

清北学堂—2020.3NOIP数学精讲营—Day 1 morning 重点笔记

qbxt Day 1 morning 重点笔记

——2020.3.8 济南 主讲：钟皓曦

1

2

3

4

最新文章

热门文章

——2020.3.8 济南主讲：钟皓曦