备孕百度之星-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)
通式：
毕达哥拉斯三元组
中国剩余定理
原根定理
每个素数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;
}
