备孕百度之星-9月13日

这段时间补了一些ACM的数论知识，用板子做了一些题目，还有很多代码量过大，较复杂的要等以后慢慢补了。下个阶段把C++的图论板子补上，就抓紧刷百度之星的题了。

一些知识

裴蜀定理：

扩展欧几里得算法:多个数加和取模

排序不等式：

两个互质的数不能凑出来的最大的数：

两个互质的数所不能表达的最大数是

a * b - a - b

不能表示的数有

\frac{(a-1)(b-1)}{2}

逆元求除法的模：

 (\frac{a}{b}) mod{\,}m = {(\frac{a}{b}) mod{\,}m} * {(bk{\,}mod{\,}m)} = {(ak{\,}mod{\,}m)}{\quad}

费马小定理

p为素数时：

{a{\,}^p}{\equiv}a{\,}(mod{\,}p) 

{a{\,}^{p-1}}{\equiv}1{\,}(mod{\,}p)

{a{\,}^{p-2}}{\equiv}{(\frac{1}{a})}{\,}(mod{\,}p)

故a的一个逆元为a^p-2 (mod p) p较大时使用快速幂

欧拉函数

F(n) 表示小于等于n和n互质的数的个数

F(1) = 1, F(p) = p - 1

积性函数

(a , b) = 1 ,=> F(a*b) = F(a) * F(b)

通式：

毕达哥拉斯三元组

中国剩余定理

https://blog.csdn.net/qq_29980371/article/details/71053219?spm=1001.2101.3001.6650.6&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBLOGCOLUMN%7Edefault-6-71053219-blog-71056337.235%5Ev38%5Epc_relevant_anti_t3_base&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBLOGCOLUMN%7Edefault-6-71053219-blog-71056337.235%5Ev38%5Epc_relevant_anti_t3_base&utm_relevant_index=5

原根定理

每个素数p都有原根，且恰好有phi(p-1)个模p的原根

原根： 设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。

佩尔方程

欧拉函数：

板子：

佩尔方程

//典型的佩尔方程
#include <cstdio>
#include <iostream>
using namespace std;

int main(){
	int x1 = 3;
	int y1 = 1;
	int px = 3;
	int py = 1;
	int d = 8;
	for(int i = 0; i < 10; i++){
		int x,y;
		x = x1 * px + d * y1 * py;
		y = y1 * px + x1 * py;
		printf("%10d%10d\n", y, (x - 1) / 2);
		px = x,py=y;
	}
	return 0;
} 

线性筛

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

#define n 100
vector<bool> a(n, true);
vector<int> prime;

int main(){
	for(int i = 2; i < n; i++){
		if(a[i]) prime.push_back(i);
		for(int j = 0; j < prime.size() && prime[j] * i < n; j++){
			a[prime[j] * i] = 0;
			if(i % prime[j] == 0) break;
		}
	}
	for(int i = 0; i < prime.size(); i++) cout << prime[i] << "   ";
	cout << endl;
}

毕达哥拉斯三元组

//判断a+b+c<=L的三角形数有几个。a^2+b^2=c^2
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
//#include<bits/stdc++.h> 
using namespace std;

#define N 1000001
bool flag[N];
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
void solve(int t)
{
	int temp,m,n,i,ans,x,y,z;
	ans=0;
	memset(flag,0,sizeof(flag));
	temp=sqrt(t+0.0);
	for(n=1;n<=temp;n++)
	{
		for(m=n+1;m<=temp;m++)
		{
			if(2*m*n+2*m*n>t)
				break;
			if(n%2!=m%2)
			{
				if(gcd(m,n)==1)
				{
					x=m*m-n*n;
					y=2*m*n;
					z=m*m+n*n;
					for(i=1;;i++)
					{
						if(i*(x+y+z)>t)
						{
							break;
						}
						ans++;
					}
				}
			}
		}
	}
	cout<<ans<<endl;
}
int main()
{
	int n;
	while(cin>>n)
	{
		solve(n);
	}
	return 0;
}

扩展欧几里得

#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>

using namespace std;
typedef long long ll; 

//用于求ax + by = (a,b)的一个解 
int exgcd(int a, int b, ll &x, ll &y){
	if(b == 0){
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b,a%b,y,x);
	y -= a/b*x;
	return d;
}

int main(){
	int a,b,m,n,l;
	ll x = 0, y = 0;
	cin >> a >> b >> m >> n >> l;
	int r = exgcd(m-n, -l, x, y);
//	int r = exgcd(21,6,x,y);
	if((a-b) % r != 0)  {
		cout << "Impossible";
	}else{
		x = (b-a)/r * x;
//		y *= (a-b)/r;
		int t = abs(l/r);
		cout << (x%t+t)%t;
	}
	return 0; 
}