清北培训Day1上午

明明说讲数学基础的，欧拉是什么鬼。
先安利一波大佬的头文件

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
	ll ans=0;
	char last=' ',ch=getchar();
	while(ch<'0' || ch>'9')last=ch,ch=getchar();
	while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
	if(last=='-')ans=-ans;
	return ans;
}
//head

NO.1 高精度运算。
基本思想：模拟加减乘除的竖式运算。
要倒叙存储。
加法（假发（紫拉）原谅我的中二之魂吧）:
1.不考虑负数。先计算，再进位。
2.考虑负数。加法变减法。
减法：
1.不考虑负数。大减小，先减后借位。小减大，转化成大减小再乘以-1。
2.考虑负数。减数为负，减变加；被减数为负，变加取负；都为负，变成被减数减减数。
乘法：
1.不考虑负数。先计算在进位。
2.考虑负数。统计负数个数，奇负偶正。
除法：
高精度/单精度：模拟竖式除法。
高精度/高精度：一般不考。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
char str[1000];
int a[1000],b[1000],c[1000];
int main(){
	scanf("%s", str);
	int len=strlen(str);
	for(int i=len-1;i>=0;i--)a[len-i]=str[i]-'0';
//	加法：scanf("%s", str);
	int n=len;
	/*len=strlen(str);
	for(int i=len-1;i>=0;i--)b[len-i]=str[i]-'0';
	int m=len;
	n=max(n,m);
	for(int i=1;i<=n;i++)c[i]=a[i]-b[i];
	for(int i=1;i<=n;i++){
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	*/
	
/*减法	for(int i=1;i<=n;i++)
		if(c[i]<0){
			c[i]+=10;
			c[i+1]-=1;
		}		
	while(c[n]==0)n-=1;*/
	
/*  乘法for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			c[i+j-1] += a[i]*b[j];
	
	for(int i=1;i<=n+m-1;i++){
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	n=n+m-1;
	while(c[n+1]>0)n+=1;*/
	int B;
/*	高精度/单精度:cin>>B;
	cout<<B<<endl;
	for(int i=n;i>0;i--){
		c[i]=a[i]/B;
		a[i-1]+=(a[i]%B)*10;
	}
	while(c[n]==0 && n>0)n--;
	for(int i=n;i>0;i--)printf("%d",c[i]);*/
	return 0;
}

No.2 膜意义下的运算
1.无除法运算。满足交换结合分配律。
a^bmod p 的思路：1.分治。2.快速幂。代码及详解
2.费马小定理：
应用：去组合数取膜（也可以用卢卡斯定理）。

3.最大公约数，最小公倍数：详解

4.指数判别：
1.sqrt判别：暴力枚举。
2.筛法：1.埃式筛法。

2.线性筛法。基本思想：使每个数只被筛一次。
5.欧拉函数：详解 代码。