数论基础模板-----数论成长之路
最大公约数gcd
gcd(f[n],f[m])=f[gcd(n,m)]
int gcd(int a, int b) //a大于b { return a % b == 0 ? b : gcd(b, a % b); }
最小公倍数Lcm
int Lcm(int a,int b) { return a/gcd(a,b)*b; }
int输入输出挂
inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f*x; } void print(int x) { if(x<0){ putchar('-');x=-x; } if(x>=10)print(x/10); putchar(x%10+'0'); }
快速幂
ll quick_pow(ll a, ull b, int mod)//二进制写法 { ll r = 1, base = a; while (b) { if (b & 1) r = (r*base) % mod; base = (base*base) % mod; b >>= 1; } return r; } int pow(int a, ull b, int m)///幂取模运算(a^b)%m(采用分治法降低时间复杂度) { int mid, ans; if (b == 0) return 1 % m; mid = pow(a, b / 2, m); ans = mid * mid % m; if (b & 1) ans = ans * a % m; return ans; }
大数快速幂
int f[1001],res[1001],sav[1001];//乘法开两倍 memset(sav, 0, sizeof(sav)); memset(f, 0, sizeof(f)); memset(res, 0, sizeof(res)); void big_pow_1() { memset(sav,0,sizeof(sav)); for(int i=1;i<=500;++i)//保存最后500位 for(int j=1;j<=500;++j) sav[i+j-1]+=res[i]*f[j];//先计算每一位的值 for(int i=1;i<=500;++i) { sav[i+1]+=sav[i]/10;//单独处理进位问题 sav[i]%=10; } memcpy(res,sav,sizeof(res));//sav赋给res } void big_pow_2() { memset(sav,0,sizeof(sav)); for(int i=1;i<=500;++i) for(int j=1;j<=500;++j) sav[i+j-1]+=f[i]*f[j]; for(int i=1;i<=500;i+=1) { sav[i+1]+=sav[i]/10; sav[i]%=10; } memcpy(f,sav,sizeof(f)); } void quick_big_pow()//快速幂模板 { //高精度赋初值 res[1]=1; f[1]=2; //2的n次方 while(p!=0) { if(p%2==1)big_pow_1(); p/=2; big_pow_2(); } } Output() { cin >> n; quick_big_pow(n); for (int i = (int)(log10(2)*n + 1); i > 0; i--) cout << res[i];//res表示最终的数组，要逆序输出 }
矩阵快速幂
//将res.a初始化为单位矩阵 struct matrix { int a[3][3]; }origin,res; matrix multiply(matrix x, matrix y) { matrix temp; memset(temp.a, 0, sizeof(temp.a)); for (int i = 0; i<2; i++) { for (int j = 0; j<2; j++) { for (int k = 0; k<2; k++) { temp.a[i][j] =(temp.a[i][j]+ x.a[i][k] * y.a[k][j])%MOD; } } } return temp; } //long long Matrix pow_matrix(long long n) { while (n) { if (n & 1) res = multiply(res, origin); n >>= 1; origin = multiply(origin, origin); } // return (res.a[0][0] + res.a[0][1])%MOD;用于题目 reutrn res; }
费马小定理
费马小定理（Fermat Theory）是数论中的一个重要定理，其内容为：假设p是质数（素数），且Gcd（a,p）=1,那么a^(p-1) ≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。该定理是1636年皮埃尔·德·费马发现的。 费马小定理在ACM数论题中应用还是较多的。
唯一分解定理
算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。（素数的分解方法唯一）
int k = 0; bool vis[100001]; int prime[100001]; void Prime()//素数筛，保存每一个素数 { memset(vis, false, sizeof(vis)); for (long long i = 2; i <= 100000; i++)//i,j用long long { if (!vis[i]) { prime[k++] = i; for (long long j = i * i; j <=100000; j += i) vis[j] = true; } } } ll fun(ll n)//把n进行素数唯一分解 { ll ans, sum; ans = 0; sum = 1; for (int i = 0;i<k&&prime[i] * prime[i] <= n; i++) { ans=0;//一定写在外面。。。太惨了 while (n%prime[i] == 0) { ans++;//指数加1 n /= prime[i]; } sum *= (2 * ans + 1); } if (n > 1)sum *= (2* 1 + 1);//如果最后还是一个素数，再处理一遍 return sum; }
拓展的欧几里得算法
扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。**已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数）如果a是负数，可以把问题转化成|a|(-x)+by=gcd(|a|,b)，然后令 x'=(-x)。通常谈到最大公约数时，我们都会提到一个非常基本的事实：给予二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)[1]。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
例如：求一对正整数（x,y）,使得**ax+by=gcd(a,b)。
提示：设a #,b,c为任意整数，如果方程ax+by=c的一组整数解为（x0,y0）,则它的任意整数解可以写成（x0+kb',y0-ka'）,其中a'=a/gcd（a,b）,b'=b/gcd(a,b),k取任意整数。
代码如下：
void exgcd(int a,int b,int &d,int & x,int & y) { if(!b){ d=a;x=1;y=0; } else { exgcd(b,a%b,d,y,x); y-=x*(a/b); } }
Eratosthenes筛法
筛法的思路的简单：对于不超过n的每个非负整数p，删除2p，3p,4p....当处理完所以的数之后，剩下的就是素数了。vis[i]表示i以及被删除，代码如下**复杂度O（nlogn）
``` memset(vis,0,sizeof(vis)); for(int i=2;i<=n;i++) for(int j=2*i;j<=n;j+=i) vis[j]=1; ``` **改进一点：**p可以限定素数，如果不是素数，则不进行第二重循环；内层循环也不必从i*2开始——它在i=2是以及被筛掉，代码如下： ``` int m=sqrt(n+0.5); memset(vis,0,sizeof(vis)); for(int i=2;i<=m;i++) if(!vis[i]) for(int j=i*i;j<=n;j+=i) vis[j]=1; ``` 素数打表（1e5循环，可以判断到1e12位是否是素数） int k = 0; bool vis[100009]; ll prime[100001]; void Prime()//素数筛，保存每一个素数 { memset(vis, false, sizeof(vis)); for (long long i = 2; i <= 100005; i++)//i,j用long long { if (!vis[i]) { prime[k++] = i; for (long long j = i * i; j <= 100005; j += i) vis[j] = true; } } }
素数定理
π(x)~x/ln(x)。
其中 ln x 为 x 的自然对数。上式的意思是当 x 趋近无限，π(x)与x/ln x的比值趋近 1。但这不表示它们的数值随着 x 增大而接近。
对正实数x，定义π(x)为素数计数函数，亦即不大于x的素数个数。
逆元
当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有b*c≡1(mod m)；
则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);
即a/b的模等于a* b的逆元的模；
逆元就是这样应用的
求逆元的方法
(1).费马小定理
在是素数的情况下，对任意整数都有。 如果无法被整除，则有。 可以在为素数的情况下求出一个数的逆元，，即为逆元。
题目中的数据范围1<=x<=10^9，p=1000000007，p是素数；
所以x肯定就无法被p整除啊，所以最后就得出x^(p-2)为x的逆元啦。
**复杂度O(logn)**
const int mod = 1000000009; long long quickpow(long long a, long long b) { if (b < 0) return 0; long long ret = 1; a %= mod; while(b) { if (b & 1) ret = (ret * a) % mod; b >>= 1; a = (a * a) % mod; } return ret; } long long inv(long long a) { return quickpow(a, mod - 2); }
2）拓展的欧几里得算法
欧几里德扩展 是用来解决 ax + by = gcd(a,b)这样的等式。
这时候取 b = MOD, 你可以写成这样 ax = gcd(a,b) - by
推导出 a*x % MOD = gcd(a,b) %MOD
所以只要 gcd(a,b) % MOD === 1时,就可以使用这条来求a的逆元
但用exgcd求得时候,inv可能是负数， 还需要进行如下操作
inv = (inv % MOD + MOD) % MOD;
long long exGcd(long long a, long long b, long long &x0, long long &y0) // a*x0 + b*y0 = gcd(a,b) { if (b == 0) { x0 = 1; y0 = 0; return a; } long long r = exGcd(b, a % b, x0, y0); long long t = x0; x0 = y0; y0 = t - a / b * y0; return r; }
1. 调用：long long inv,y0;
2. exGcd(n ,MOD,inv,y0);
3. inv = (inv % MOD + MOD) % MOD;
（3）逆元打表
const int N = 100005; long long _inv[N]; void pre() { _inv[0] = _inv[1] = 1; for (int i = 2; i < N; i++) { _inv[i] = ((MOD - MOD / i) * _inv[MOD % i]) % MOD; } }
大数模板
紫书大数模板
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string.h> #include<vector> #include<string> #include<algorithm> using namespace std; struct BigIterger { static const int Base = 100000000; static const int Width = 8; vector<int>s; BigIterger(long long num = 0) { *this = num; }//构造函数 BigIterger operator=(long long num) { s.clear(); do { s.push_back(num%Base); num /= Base; } while (num > 0); return *this; } BigIterger operator=(const string &str) { s.clear(); int y, len = (str.length() - 1) / Width + 1; for (int i = 0; i <len; i++) { int end = str.length() - i * Width; int strat = max(0, end - Width); string x = str.substr(strat, end - strat);//substr截取一段 y = atoi(x.c_str());//c_str()将string变成const char*C语言库函数名: atoi功 能 : 把字符串转换成整型数 s.push_back(y); } return *this; } BigIterger operator+(const BigIterger &b)const { BigIterger c; c.s.clear(); for (int i = 0, g = 0;; i++) { if (g == 0 && i >= s.size() && i >= b.s.size())break; int x = g; if (i < s.size())x += s[i]; if (i < b.s.size())x += b.s[i]; c.s.push_back(x%Base); g = x / Base; } return c; } BigIterger operator+=(const BigIterger &b) { *this = *this + b; return *this; } bool operator<(const BigIterger &b)const { if (s.size() != b.s.size())return s.size() < b.s.size(); for (int i = s.size() - 1; i >= 0; i--) if (s[i] != b.s[i])return s[i] < b.s[i]; return false;//== } bool operator>(const BigIterger& b)const { return b < *this; } bool operator<=(const BigIterger& b)const { return !(b < *this); } bool operator>=(const BigIterger& b)const { return !(b>*this); } bool operator!=(const BigIterger& b)const { return b>*this||b<*this; } bool operator==(const BigIterger& b)const { return !(b>*this)&&! (b<*this); } }; ostream& operator << (ostream &out, const BigIterger& x) { out << x.s.back(); for (int i = x.s.size()-2; i >= 0; i--) { char buf[30]; sprintf(buf, "%08d", x.s[i]); for (int j = 0; j < strlen(buf); j++)out << buf[j]; } return out; } istream& operator >> (istream &in, BigIterger & x) { string s; if (!(in >> s))return in; x = s; return in; }
大数+打表 nt a[100], b[100], c[100]; string str[200]; str[1] = "4"; str[2] = "14"; for (int i = 3; i <= 100; i++) { int strL1 = str[i - 2].size(); int strL2 = str[i - 1].size(); memset(a, 0, sizeof a); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); for (int j = 0; j < strL1; j++)a[strL1 - j] = str[i - 2][j] - '0'; for (int j = 0; j < strL2; j++)b[strL2 - j] = str[i - 1][j] - '0'; for (int j = 1; j <= strL2; j++)b[j] *= 4; for (int j = 1; j <= strL2; j++)b[j + 1] += b[j] / 10, b[j] = b[j] % 10; while (b[strL2 + 1] != 0)strL2++; int len = strL2; for (int j = 1; j <= len; j++) c[j] = b[j] - a[j]; for (int j = 1; j <= len; j++) if (c[j] < 0) { c[j] = c[j] + 10; c[j + 1]--; } while (c[len] == 0) len--; string temp = ""; for (int j = len; j >= 1; j--) temp += '0' + c[j]; str[i] = temp; }
投递旷视等公司10个岗位 >