1.2万

GTAlgorithm

shenjingwa

mouzaisi

yinyyy
Amazing_
qyzawa_phi
Xinqwq

zxt
lukelmouse

## $中国剩余定理$

#### $2.相关定理$

$中国剩余定理：若m_1, m_2, …m_n满足两两互质,M = \prod_{i = 1}^{n}{m_i}, M_i = \frac{M}{m_i}, t_i满足 \\ t_i, M_i \equiv 1(\mod {m_i}). 对于任意的n个整数a_1, a_2,…a_n,方程组：$

\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\cdots \\
x \equiv a_2 \pmod{m_n} \\
\end{cases}

## $例题$

#### 问题描述：

$\quad \quad \quad \quad 给定一个方程组：$
\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\cdots \\
x \equiv a_2 \pmod{m_n} \\
\end{cases}

#### $其中m数组两两互质,求该方程组的正整数解.$

输入样例：
3
3 1
5 1
7 2

16


## $代码：$

#include<cstdio>
using namespace std;
const int N = 1e6 + 1;
#define ll long long
ll n, a[N], b[N];
ll M = 1;
ll ans = 0;
ll exgcd(ll a, ll b, ll &x, ll&y){
if(!b){
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
ll d, x, y;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++)
scanf("%lld%lld",&a[i], &b[i]);
for(int i = 1;i <= n;i ++)
M *= a[i];
for(int i = 1;i <= n;i ++){
exgcd(M / a[i], a[i], x, y);
ans = (ans + b[i] * x * M / a[i] % M + M) % M;
}
printf("%lld",ans);
}


#### 例如：$A = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \\ \end{bmatrix}$, $B = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \ \end{bmatrix} .$

$$A * B = \begin{bmatrix} 1 * 1 + 4 * 4 & 1 * 2 + 4 * 5 & 1 * 3 + 4 * 6 \\ 2 * 1 + 5 * 4 & 2 * 2 + 5 * 5 & 2 * 3 + 5 * 6 \\ 3 * 1 + 6 * 4 & 3 * 2 + 6 * 5 & 3 * 3 + 6 * 6 \end{bmatrix} = \begin{bmatrix} 17 & 22 & 27 \\ 22 & 29 & 36 \\ 27 & 36 & 45 \end{bmatrix}$$

### 题目描述

#### C++ 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MOD 2017
const int N = 101;
struct matrix{
int a[N][N];
void clear(){
for(int i = 1;i < N;i ++)
for(int j = 1;j < N;j ++)
a[i][j] = (i == j);
}
matrix operator * (const matrix & x) const{
matrix c;
for(int i = 1;i < N;i ++)
for(int j = 1;j < N;j ++){
c.a[i][j] = 0;
for(int k = 1;k < N;k ++)
c.a[i][j] = (c.a[i][j] + (a[i][k] * x.a[k][j]) % MOD) % MOD;
}
return c;
}
};
int n, m, t;
matrix map;
matrix qmi(matrix a, int b){
matrix ret;
ret.clear();
while(b){
if(b & 1) ret = ret * a;
a = a * a;
b >>= 1;
}
return ret;
}
int main(){
int u, v;
scanf("%d%d",&n,&m);
map.clear();
for(int i = 0;i < m;i ++){
scanf("%d%d",&u,&v);
map.a[u][v] = map.a[v][u] = 1;
}
for(int i = 1;i <= n + 1;i ++)
map.a[i][n + 1] = 1;
scanf("%d",&t);
matrix a;
memset(a.a, 0, sizeof(a.a));
a.a[1][1] = 1;
a = a * qmi(map, t);
int ans = 0;
for(int i = 1;i <= n + 1;i ++)
ans = (ans + a.a[1][i]) % MOD;
printf("%d\n", ans);
return 0;
}


### 题目描述

#### C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
const int N = 1e6 + 1;
int prime[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int maxd;
int number;
int n;
void dfs(int u, int last, int p, int s){
if(s > maxd || s == maxd && p < number){
maxd = s;
number = p;
}
if(u == 9) return ;
for(int i = 1;i <= last;i ++){
if((ll)p * prime[u] > n) break;
p *= prime[u];
dfs(u + 1, i, p, s * (i + 1));
}
}
int main(){
scanf("%d",&n);
dfs(0, 30, 1, 1);
printf("%d\n", number);
return 0;
}


### $题目描述$

#### C++ 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e6 + 40;

typedef long long LL;

int primes[N],cnt;
bool st[N];

void get_primes(int n)
{
memset(st, false, sizeof(st));
cnt = 0;
for(int i = 2;i <= n;i ++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; primes[j] <= n / i;j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}

int main()
{
long long l, r;
while (cin >> l >> r)
{
get_primes(50000);

memset(st, false, sizeof st);
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];

for (long long j = max((l + p - 1) / p * p, 2ll * p); j <= r; j += p)
st[j - l] = true;
}

cnt = 0;
for (int i = 0; i <= r - l; i ++ )
if (!st[i] && i + l > 1)
primes[cnt ++ ] = i + l;

if (cnt < 2) puts("There are no adjacent primes.");
else
{
int minp = 0, maxp = 0;
for (int i = 0; i + 1 < cnt; i ++ )
{
int d = primes[i + 1] - primes[i];
if (d < primes[minp + 1] - primes[minp]) minp = i;
if (d > primes[maxp + 1] - primes[maxp]) maxp = i;
}

printf("%d,%d are closest, %d,%d are most distant.\n", primes[minp], primes[minp + 1], primes[maxp], primes[maxp + 1]);
}
}
return 0;
}


### 题目描述

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
ll f[N];
ll n, d, k;
ll x[N], s[N];
inline bool check(int p){
ll now = 0;
memset(f, 0 ,sizeof(f));
deque<int>q;
ll lg = max(1 * 1ll, d - p), rg = d + p;
for(int i = 1;i <= n;i ++){
while(x[now] + lg <= x[i]){
while(!q.empty() && f[q.back()] < f[now])
q.pop_back();
q.push_back(now);
now ++;
}
while(!q.empty() && x[q.front()] + rg < x[i])
q.pop_front();
if(!q.empty())
f[i] = f[q.front()] + s[i];
else
f[i] = -1e18;
if(f[i] >= k)
return true;
}
return false;
}
int main(){
scanf("%lld%lld%lld",&n,&d,&k);
for(int i = 1;i <= n;i ++)
scanf("%lld%lld",&x[i],&s[i]);
int l = 0, r = x[n] + 1;
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%lld", (l == x[n] ? -1 : l));
return 0;
}


## $并且将新的元素加入队尾。$

### 算法1

#### C++ 代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

typedef long long ll;

const int N = 1e7 + 1;
const int M = 1e4 + 1;
const int MAXN = 1e3 + 1;
int h, t;
int n, k, a[N], w[N], v[N];
void maxx(){
h = 1, t = 0;
for(int i = 1;i <= n;i ++){
while(t >= h && w[t] < a[i]) -- t;
w[++ t] = a[i];
v[t] = i;
while(v[h] <= i - k) ++ h;
if(i >= k) printf("%d ", w[h]);
}
}
void minn(){
for(int i = 1;i <= n;i ++){
while(t >= h && w[t] > a[i]) -- t;
w[++ t] = a[i];
v[t] = i;
while(v[h] <= i - k && h < t) ++ h;
if(i >= k) printf("%d ", w[h]);
}
printf("\n");
}
int main(){
cin >> n >> k;
for(int i = 1;i <= n;i ++) cin >> a[i];
minn();
maxx();
return 0;
}


## $这题需要转化为三进制，然后从k往前dp，再从k往后dp，两个方案数相乘即是答案。$

### 算法1

#### C++ 代码

#include<cstdio>
using namespace std;
const int N = 1e4 + 1;
const int mod = 1e6;
#define ll long long
ll dp[N][251];
ll mp[N];
ll n, m, k, cnt;
ll sta;
ll st[N];
bool check(ll a){
ll tmp = -1, last = -1;
for(int i = 1;i <= m;i ++){
tmp = a % 3;
if(tmp == last)
return false;
last = tmp;
a /= 3;
}
return true;
}
ll qmi(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = 1ll * res * a;
a = 1ll * a * a;
b >>= 1;
}
return res;
}
bool judge(ll a, ll b){
for(int i = 1;i <= m;i ++){
if(a % 3 == b % 3) return false;
a /= 3;
b /= 3;
}
return true;
}
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i = 1;i <= m;i ++){
scanf("%lld",&mp[i]);
sta = sta * 3 + mp[i] - 1;
}
ll maxx = qmi(3, m);
cnt = 0;
for(int i = 0;i < maxx;i ++){
if(check(i))
st[++cnt] = i;
}
ll pos = -1;
for(int i = 1;i <= cnt;i ++){
if(st[i] == sta){
pos = i;
break;
}
}
if(pos == -1){
puts("0");
return 0;
}
dp[k][pos] = 1;
for(int i = k - 1;i >= 1;i --)
for(int j = 1;j <= cnt;j ++)
for(int k = 1;k <= cnt;k ++)
if(judge(st[j], st[k]))
dp[i][j] = (dp[i][j] + dp[i + 1][k]) % mod;
for(int i = k + 1;i <= n;i ++)
for(int j = 1;j <= cnt;j ++)
for(int k = 1;k <= cnt;k ++)
if(judge(st[j], st[k]))
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
ll ans1 = 0, ans2 = 0;
// ans1为第k行上方的方案数，ans2是第k行下方的方案数目
for(int i = 1;i <= cnt;i ++)
ans1 = (ans1 + dp[1][i]) % mod;
for(int i = 1;i <= cnt;i ++)
ans2 = (ans2 + dp[n][i]) % mod;
if(k == 1)
printf("%lld\n", ans2);
else if(k == n)
printf("%lld\n", ans1);
else
printf("%lld\n", ans1 * ans2 % mod);
return 0;
}



## $最后的答案就是：f[(1 << n) - 1][n - 1];$

### 算法1

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, f[1 << N][N + 1];
int a[N + 1][N + 1];
int main(){
memset(f, 0x3f, sizeof(f));
cin >> n;
for(int i = 0;i < n;i ++)
for(int j = 0;j < n;j ++)
cin >> a[i][j];
f[1][0] = 0;
for(int i = 1;i < (1 << n);i ++)
for(int j = 0;j < n;j ++)
if((i >> j) & 1)
for(int k = 0;k < n;k ++)
if((i ^ (1 << j)) >> k & 1)
f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + a[k][j]);
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}


## $所以我们枚举主件，对这5种情况分别转移即可。$

#### 样例

样例输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

2200



### 算法1

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
const int M = 5e3 + 1;
int n, m;
int mw[N], mc[N], aw[M][M], ac[M][M];
int f[N];
int main(){
cin >> n >> m;
for(int i = 1;i <= m;i ++){
int v, p, q;
cin >> v >> p >> q;
if(!q){
mw[i] = v;
mc[i] = v * p;
}
else{
++ aw[q][0];
aw[q][aw[q][0]] = v;
ac[q][aw[q][0]] = v * p;
}
}
for(int i = 1;i <= m;i ++)
for(int j = n;mw[i] != 0 && j >= mw[i];j --){
f[j] = max(f[j], f[j - mw[i]] + mc[i]);
if(j >= mw[i] + aw[i][1])
f[j] = max(f[j], f[j - mw[i] - aw[i][1]] + mc[i] + ac[i][1]);
if(j >= mw[i] + aw[i][2])
f[j] = max(f[j], f[j - mw[i] - aw[i][2]] + mc[i] + ac[i][2]);
if(j >= mw[i] + aw[i][1] + aw[i][2])
f[j] = max(f[j], f[j - mw[i] - aw[i][1] - aw[i][2]] + mc[i] + ac[i][1] + ac[i][2]);
}
cout << f[n] << endl;
return 0;
}