数论模板
就保存一下模板
//递推
#include <cstdio>
#include <cstring>
#include <algorithm>
long long inv[3000010];
int main() {
int n,p;
scanf("%d%d",&n,&p);
inv[1] = 1;
printf("1
");
for(int i = 2; i <= n; i++)
{
inv[i] = ((1ll * (-p / i) * inv[p % i] % p) + p) % p;
printf("%d
",inv[i]);
}
return 0;
}
// 费马小定理 p为素数
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int poww(long long a,long long b)
{
long long temp = 1,p = b-2;
while(p)
{
if(p&1 == 1) temp = temp*a%b;
a = a*a % b;
p >>= 1;
}
return temp;
}
int main() {
int n,p;
scanf("%d%d",&n,&p);
for(int i = 1; i <= n; i++)
{
long long ans = 0;
ans = poww(i,p);
printf("%lld
",ans);
}
return 0;
}
还有个exgcd
欧拉定理/扩展欧拉定理
//单点求phi 模板题ac
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
long long a, m, b, flag, ans = 1, phi, tmp;
char t;
void ksm(long long a, long long b, long long c) {
a %= c;
while(b) {
if(b & 1) {
ans = (ans * a) % c;
}
a = (a * a) % c;
b >>= 1;
}
}
int main() {
scanf("%lld%lld", &a, &m);
tmp = phi = m;
for(long long i = 2; i * i <= m; i++) {
if(tmp % i == 0) {
phi -= (phi / i);
while(tmp % i == 0) {
tmp /= i;
}
}
}
if(tmp > 1)
phi -= (phi / tmp);
while(!isdigit(t = getchar()));
for(; isdigit(t); t = getchar()) {
b = b * 10 + t - '0';
if(b >= phi) {
flag = 1;
b %= phi;
}
}
if(flag) {
b += phi;
}
ksm(a, b, m);
printf("%lld", ans);
return 0;
}
//递推求phi 模板题24分
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
typedef int int_;
#define int long long
bool vis[1000007];
int pri[1000007], phi[1000007], cnt, temp, ans, lenm, lent, bns, m, a;
char strr[20000007];
inline void getphi(int n) {
vis[0] = vis[1] = 1;
phi[1] = 1;
for(int i = 2; i <= n; i++)
{
if(vis[i] == 0)
{
pri[++cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && pri[j] * i <= n; j++)
{
int next = pri[j] * i;
vis[next] = 1;
if(i % pri[j] == 0)
{
phi[next] = phi[i] * pri[j];
break;
}
phi[next] = phi[i] * (pri[j] - 1);
}
}
}
inline int ksm(int a, int b, int mod)
{
int ret = 1;
while(b > 0)
{
if(b & 1) ret *= a, ret %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return ret;
}
int_ main() {
scanf("%lld%lld", &a, &m);
getphi(m);
lenm = phi[m];
while(lenm > 0)
{
lenm /= 10;
lent++;
}
scanf("%s", strr);
int len = strlen(strr), t = 1;
for(int i = len - 1; i >= 0; i--)
{
temp = strr[i] - '0';
ans += (t * temp);
ans %= phi[m];
t *= 10;
t %= phi[m];
}
ans %= phi[m];
bns = ksm(a, ans, m);
if(ans == 0) bns = 0;
printf("%lld", bns);
return 0;
}
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef int int_;
#define int long long
const int mod = 1e9 + 7;
struct MAT{
int A[110][110];
int x, y;
MAT(int x_, int y_)
{
x = x_, y = y_;
for(int i = 1; i <= x; i++)
for(int j = 1; j <= y; j++)
A[i][j] = 0;
}
void init(bool flg)
{
for(int i = 1; i <= x; i++)
for(int j = 1; j <= y; j++)
A[i][j] = 0;
if(flg)
for(int i = 1; i <= x; i++) A[i][i] = 1;
}
MAT operator*(MAT b)
{
MAT a = *this;
MAT c(a.x, b.y);
c.init(0);
for(int i = 1; i <= a.x; i++)
for(int j = 1; j <= b.y; j++)
for(int l = 1; l <= a.y; l++)
{
c.A[i][j] += a.A[i][l] * b.A[l][j];
c.A[i][j] %= mod;
}
return c;
}
MAT operator^(int b)
{
MAT ret(x, x), a = *this;
ret.init(1);
while(b)
{
if(b&1) ret = ret * a;
b >>= 1;
a = a * a;
}
return ret;
}
void output()
{
for(int i = 1; i <= x; i++)
{
for(int j = 1; j <= y; j++)
printf("%lld ", A[i][j]);
puts("");
}
}
};
int_ main() {
int n, m, k;
scanf("%lld%lld", &n, &k);
MAT a(n, n);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%lld", &a.A[i][j]);
MAT c = a ^ k;
c.output();
}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//I AK IOI
long long T, n, m, p;
long long jc[100007];
long long ksm(long long a, long long b, long long c) {
a %= c;
long long ret = 1;
while(b != 0) {
if(b & 1) ret = ret * a % c;
b >>= 1;
a = a * a % c;
}
return ret % c;
}
long long cm(long long a, long long b, long long c) {
if(b > a) return 0;
return (jc[a] * ksm(jc[b], c - 2, c) % c * ksm(jc[a - b], c - 2, c) % c) % c;
}
long long lucas(long long a, long long b, long long c) {
if(b == 0) return 1;
return cm(a % c, b % c, c) * lucas(a / c, b / c, c) % c;
}
int main() {
scanf("%lld", &T);
jc[0] = 1;
while(T--) {
scanf("%lld%lld%lld", &n, &m, &p);
for(long long i = 1; i <= p; i++) jc[i] = jc[i - 1] * i % p;
printf("%lld
", lucas(m + n, n, p));
}
}
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef int int_;
#define int long long
const int mod = 1e9 + 7;
struct MAT{
int A[110][110];
int x, y;
MAT(int x_, int y_)
{
x = x_, y = y_;
for(int i = 1; i <= x; i++)
for(int j = 1; j <= y; j++)
A[i][j] = 0;
}
void init(bool flg)
{
for(int i = 1; i <= x; i++)
for(int j = 1; j <= y; j++)
A[i][j] = 0;
if(flg)
for(int i = 1; i <= x; i++) A[i][i] = 1;
}
MAT operator*(MAT b)
{
MAT a = *this;
MAT c(a.x, b.y);
c.init(0);
for(int i = 1; i <= a.x; i++)
for(int j = 1; j <= b.y; j++)
for(int l = 1; l <= a.y; l++)
{
c.A[i][j] += a.A[i][l] * b.A[l][j];
c.A[i][j] %= mod;
}
return c;
}
MAT operator^(int b)
{
MAT ret(x, x), a = *this;
ret.init(1);
while(b)
{
if(b&1) ret = ret * a;
b >>= 1;
a = a * a;
}
return ret;
}
};
int_ main() {
int T;
scanf("%lld", &T);
while(T--)
{
int q;
scanf("%lld", &q);
if(q <= 3)
{
printf("1
");
continue;
}
MAT ans(3, 3), chen(3, 1);
ans.A[1][1] = ans.A[1][3] = ans.A[2][1] = ans.A[3][2] = 1;
chen.A[1][1] = chen.A[2][1] = chen.A[3][1] = 1;
ans = ans ^ (q - 3);
ans = ans * chen;
printf("%lld
", ans.A[1][1]);
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int poww(long long a,long long b,long long c)
{
long long temp = 1;
while(b)
{
if(b&1 == 1) temp = temp*a%c;
a = a * a % c;
b >>= 1;
}
return temp;
}
int main() {
long long b,p,k,ans;
scanf("%lld%lld%lld",&b,&p,&k);
ans = poww(b,p,k)%k;
printf("%d^%d mod %d=%d",b,p,k,ans);
return 0;
}
excrt
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long n, a[100007], p[100007];
long long ksc(long long x, long long y, long long mod) {
long long ret = 0;
while(y > 0) {
if(y & 1) ret = (ret + x) % mod;
y >>= 1;
x = (x + x) % mod;
}
return (ret % mod + mod) % mod;
}
long long exgcd(long long m, long long n, long long &x, long long &y) {
if(n == 0) {
x = 1;
y = 0;
return m;
}
long long res = exgcd(n, m % n, y, x);
y -= (m / n) * x;
return res;
}
long long excrt() {
long long A = a[1], P = p[1], x, y;
for(long long i = 2; i <= n; i++) {
long long a1 = P, b1 = p[i], c = ((a[i] - A) % b1 + b1) % b1;
long long gcd = exgcd(a1, b1, x, y), bg = b1 / gcd;
if(c % gcd != 0) return -1;//判无解
x = ksc(x, c / gcd, bg);
A += x * P;
P *= bg;
A = (A % P + P) % P;
}
if(A == 0) A = P;
return A;
}
int main() {
// freopen("111.in", "r", stdin);
scanf("%lld", &n);
for(long long i = 1; i <= n; i++) {
scanf("%lld%lld", &p[i], &a[i]);
}
printf("%lld", excrt());
return 0;
}