$\href{https://www.acwing.com/blog/content/34755/}{codeforce 每日一题}$

2.1万

ylimhs
Lowbcgz

itdef

acwing_07540
Narity
wujiay

aio
CAI__CAI

j30
H_z_xiao

h.john
tonngw

### 算法

#### C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

LL n, m, t;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin>>n>>t;

vector<PLL> w(n + 2, {0, 0});
rep(i, 1, n) cin>>w[i].fi>>w[i].se;
w[n + 1].fi = t + 1, w[0].fi = 1;

LL res = 0, last = 0;
rep(i, 0, n)
{
last += w[i].se;
res += min(last, w[i + 1].fi - w[i].fi);
last = max(0ll, last - (w[i + 1].fi - w[i].fi));
//  cout<<res<<" "<<last<<endl;
}

cout<<res<<endl;

return 0;
}


#### Java 代码

import java.util.*;

public class Main{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextLong();
long[] d = new long[n + 10];
long[] t = new long[n + 10];
for(int i=1;i<=n;i++) {d[i] = sc.nextLong();t[i] = sc.nextLong();}
d[0] = 1;d[n + 1] = k + 1;
long res = 0, last = 0;
for(int i=0;i<=n;i++)
{
last += t[i];
res += Math.min(last, d[i+1] - d[i]);
last = Math.max(0, last - (d[i+1] - d[i]));
}

System.out.println(res);
}
}


#### Python 代码

n, k = map(int, input().split())

d, t = [0] * (n + 2), [0] * (n + 2)

for i in range(1, n + 1): d[i], t[i] = map(int, input().split())

res, last = 0, 0
d[0], d[n + 1] = 1, k + 1

for i in range(n + 1):
last += t[i]
res += min(last, d[i + 1] - d[i])
last = max(0, last - (d[i + 1] - d[i]))

print(res)


//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

LL n, m, t;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin>>n>>t;

vector<PLL> w(n + 2, {0, 0});
rep(i, 1, n) cin>>w[i].fi>>w[i].se;
w[n + 1].fi = t + 1, w[0].fi = 1;

LL res = 0, last = 0;
rep(i, 0, n)
{
last += w[i].se;
res += min(last, w[i + 1].fi - w[i].fi);
last = max(0ll, last - (w[i + 1].fi - w[i].fi));
//  cout<<res<<" "<<last<<endl;
}

cout<<res<<endl;

return 0;
}


### 题目描述

1. 1≤a[1]≤a[2]≤…≤a[n]≤u。
2. a[i] 整除 a[i+1]（或者说 a[i] 是 a[i+1] 的因子）。

#### 样例

##### 输入样例1
3 2

##### 输出样例1
5

##### 输入样例2
6 4

##### 输出样例2
39


### 算法

#### C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2000 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9+7;

int n, m;
LL f[N][N];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin>>m>>n;

rep(i, 1, m) f[1][i] = 1;
rep(i, 2, n)
rep(j, 1, m)
rep(k, 1, m)
if(k * j <= m) f[i][k * j] = (f[i][k * j] + f[i - 1][j]) % mod;
else break;

LL res = 0;
rep(i, 1, m) res = (res + f[n][i]) % mod;

cout<<res<<endl;

return 0;
}


#### Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f, mod = 1000000007;

public static void solve()
{
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();int n = sc.nextInt();
long[] f = new long[m + 1];
f[1] = 1;
for(int i = 0; i < n; i ++)
for(int j = m; j > 0; j --)
for(int k = j * 2; k <= m; k += j)
f[k] = (f[k] + f[j]) % mod;
long res = 0;
for(int i = 1; i <= m; i ++) res = (res + f[i]) % mod;
System.out.println(res);
}

public static void main(String[] args)
{
solve();
}
}


#### Python 代码

#  https://www.acwing.com/blog/content/34755/

mod = int(1e9 + 7)

def solve():
m, n = map(int, input().split())

f = [0] * (m + 1)
f[1] = 1
for i in range(n):
for j in range(m, 0, -1):
k = j * 2
while k <= m:
f[k] = (f[k] + f[j]) % mod
k += j

res = sum(f[1 : m + 1])
print(res % mod)

def main():
solve()

if __name__ == '__main__':
main()


### 算法

#### C++ 代码

//  codeforce每日一题  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;
int g[11][11], dist[11][11];

int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

cin>>n;
rep(i, 1, n)
rep(j, 1, n) cin>>g[i][j];

rep(k, 1, n)
rep(i, 1, n)
rep(j, 1, n)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

int res = 0;
rep(i, 1, n)
rep(j, 1, n)
res = max(res, g[i][j]);
cout<<res<<endl;

return 0;
}



### 算法

#### C++ 代码

//  codeforce每日一题  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> PIII;
typedef pair<double, double> PDD;

const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;
char str[N];
int w[N], ne[N], pre[N];

int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

cin>>n>>str + 1;
rep(i, 1, n) cin>>w[i], ne[i] = i + 1, pre[i] = i - 1;

set<int> s;
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
rep(i, 1, n - 1)
if(str[i]!=str[i+1])
heap.push({abs(w[i] - w[i + 1]), {i, i + 1}});

vector<PIII> res;
while(heap.size())
{
auto u = heap.top();
heap.pop();
if(s.count(u.se.fi) || s.count(u.se.se)) continue;
res.pd({u.fi,{u.se.fi, u.se.se}});
if(pre[u.se.fi]!=0 &&
ne[u.se.se]!=n+1 &&
str[pre[u.se.fi]]!=str[ne[u.se.se]])
heap.push({abs(w[pre[u.se.fi]] - w[ne[u.se.se]]), {pre[u.se.fi], ne[u.se.se]}});
pre[ne[u.se.se]] = pre[u.se.fi];
ne[pre[u.se.fi]] = ne[u.se.se];
s.insert(u.se.se);s.insert(u.se.fi);
}

//  sort(all(res));
cout<<res.size()<<endl;
for(auto u : res) cout<<u.se.fi<<" "<<u.se.se<<endl;

return 0;
}


### 题目描述

#### 样例

##### 输入样例1
(())(()
()))()

##### 输出样例1
(())()()

##### 输入样例2
)
((

##### 输出样例2
(())

##### 输入样例3
)
)))

##### 输出样例3
((()))

##### 输入样例4
())
(()(()(()(

##### 输出样例4
(()()()(()()))


### 算法

#### C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int ma[210][210][410];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

memset(ma, -1, sizeof ma);
string str1, str2;
cin>>str1>>str2;
n = str1.size(), m = str2.size();

str1 += "!", str2 += "!";

int tmp = 0;
function<int(int,int,int)> dfs = [&](int l, int r, int k){
if(k > n + m) return INF;
if(l == n && r == m && !k) return 0;
if(ma[l][r][k]!=-1) return ma[l][r][k];
ma[l][r][k] = INF;
int res = dfs(l + (str1[l]=='('), r + (str2[r] == '('), k + 1) + 1;
if(k > 0) res = min(res, dfs(l + (str1[l] == ')'), r + (str2[r] == ')'), k - 1) + 1);
ma[l][r][k] = res;
return res;
};

string res;
function<void(int,int,int)> f = [&](int l, int r, int k){
if(l==n && r==m && !k) return;

if(dfs(l + (str1[l] == '('), r + (str2[r] == '('), k + 1) + 1 == dfs(l, r, k)){
res.push_back('(');
f(l + (str1[l] == '('), r + (str2[r] == '('), k + 1);
}else res.push_back(')'), f(l + (str1[l] == ')'), r + (str2[r] == ')'), k - 1);
};
f(0, 0, 0);
cout<<res<<endl;

return 0;
}


### 题目描述

#### 样例

##### 输入样例1
4 2
1 2 1 2

##### 输出样例1
3

##### 输入样例2
5 3
1 2 1 1 3

##### 输出样例2
2

##### 输入样例3
3 1
1 1 1

##### 输出样例3
6


### 算法

#### C++ 代码

//  codeforce每日一题  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, m;

int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

cin>>n>>m;
vector<int> w(n + 1);
map<int,int> g;
rep(i, 1, n) cin>>w[i];

LL res = 0, cnt = 0;
for(int i=1,j=0;i<=n;i++){
g[w[i]] ++;
if(g[w[i]]==m) cnt++;
while(j<i){
g[w[j + 1]] --;
if(g[w[j + 1]]==m-1) cnt--;
if(cnt==0){
g[w[j + 1]]++;
if(g[w[j + 1]] == m) cnt++;
break;
}
else j++;
}
//  cout<<cnt<<" "<<j<<endl;
if(cnt) res += j + 1;
}

cout<<res<<endl;

return 0;
}


#### Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{
public static void solve()
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[] w = new int[n + 1];
for(int i=1;i<=n;i++) w[i] = sc.nextInt();
Map<Integer, Integer> g = new HashMap<Integer, Integer>();
long res = 0, cnt = 0;
int tmp;
for(int i=1,j=0;i<=n;i++){
if(g.containsKey(w[i])){
tmp = g.get(w[i]);
g.remove(w[i]);
g.put(w[i], tmp + 1);
}else g.put(w[i], 1);

if(g.get(w[i])==m) cnt++;
while(j<i){
tmp = g.get(w[j + 1]);
g.remove(w[j + 1]);
g.put(w[j + 1], tmp - 1);
if(g.containsKey(w[j + 1]) && g.get(w[j + 1])==m-1) cnt--;
if(cnt==0){
if(g.containsKey(w[j + 1])){
tmp = g.get(w[j + 1]);
g.remove(w[j + 1]);
g.put(w[j + 1], tmp + 1);
}else g.put(w[j + 1], 1);
if(g.get(w[j + 1]) == m) cnt++;
break;
}
else j++;
}
//  cout<<cnt<<" "<<j<<endl;
if(cnt > 0) res += j + 1;
}
System.out.println(res);
}

public static void main(String args[])
{
solve();
}
}


#### Python 代码

#  https://www.acwing.com/blog/content/34755/

def solve():
n, m = map(int, input().split())
w = [int(i) for i in input().split()]
w.insert(0, 0)

g = {}
res, cnt = 0, 0
j = 0
for i in range(1, n + 1):
g[w[i]] = g.get(w[i], 0) + 1
if g[w[i]] == m: cnt += 1
while j < i:
g[w[j + 1]] = g[w[j + 1]] - 1
if g[w[j + 1]] == m - 1: cnt -= 1
if cnt == 0:
if g[w[j + 1]] == m - 1: cnt += 1
g[w[j + 1]] = g[w[j + 1]] + 1
break
else: j += 1

if cnt > 0: res += j + 1
print(res)

def main():
solve()

if __name__ == '__main__':
main()


### 题目描述

#### 样例

##### 输入样例1
3
-1 2 3

##### 输出样例1
0 1 3

##### 输入样例2
4
0 0 -1 0

##### 输出样例2
0 0 0

##### 输入样例3
1
10000

##### 输出样例3
1 1 1


### 算法

#### C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin>>n;
vector<int> w(n + 1);
rep(i, 1, n) cin>>w[i];

vector<LL> s(n + 1, 0);
vector<PLL> g1(n + 2, {0, 0}), g2(n + 2, {0, 0});
rep(i, 1, n) s[i] += s[i - 1] + w[i];
rep(i, 1, n){
g1[i].fi = max(g1[i-1].fi, s[i]);
if(g1[i].fi==s[i]) g1[i].se = i;
else g1[i].se = g1[i-1].se;
}
g2[n + 1] = {-1e18, 0};
per(i, 1, n)
{
g2[i].fi = max(g2[i+1].fi, s[i]);
if(g2[i].fi==s[i]) g2[i].se = i;
else g2[i].se = g2[i+1].se;
}

LL res = -1e18;
vector<int> ans(3);
rep(i, 0, n){
LL tmp = g1[i].fi - s[i] + g2[i].fi;
if(res<tmp){
res = tmp;
ans[0] = g1[i].se, ans[1] = i, ans[2] = g2[i].se;
}
}
cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<endl;

return 0;
}


#### Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f;

public static void solve()
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] w = new int[n + 1];
for(int i=1;i<=n;i++) w[i] = sc.nextInt();
long[] s = new long[n + 1];
long[] g = new long[n + 1];
int[] idx = new int[n + 1];
for(int i=1;i<=n;i++) s[i] = s[i - 1] + w[i];
for(int i=1;i<=n;i++){
g[i] = Math.max(g[i - 1], s[i]);
if(g[i] == s[i]) idx[i] = i;
else idx[i] = idx[i - 1];
}
long res = -1000000000;
int[] ans = new int[3];
long S = s[n];
int idx1 = n;
for(int i=n;i>=0;i--)
{
if(s[i] > S){
S = s[i];
idx1 = i;
}
long tmp = g[i] - s[i] + S;
if(tmp > res)
{
res = tmp;
ans[0] = idx[i];ans[1] = i; ans[2] = idx1;
}
}
System.out.printf("%d %d %d", ans[0], ans[1], ans[2]);
}

public static void main(String[] args)
{
solve();
}
}


#### Python 代码

#  https://www.acwing.com/blog/content/34755/

def solve():
n = int(input())
w = [int(i) for i in input().split()]
w.insert(0, 0)
s = [0] * (n + 1)
for i in range(1, n + 1): s[i] = s[i - 1] + w[i]
g1 = [0] * (n + 1)
idx = [0] * (n + 1)
for i in range(1, n + 1):
g1[i] = max(g1[i - 1], s[i])
if g1[i] == s[i]: idx[i] = i
else: idx[i] = idx[i - 1]
res = -1e18
S, idx1 = s[n], n
for i in range(n, -1, -1):
if S < s[i]:
S = s[i]
idx1 = i
tmp = g1[i] - s[i] + S
if tmp > res:
res = tmp
#  print(res)
ans = [idx[i], i, idx1]
print(ans[0], ans[1], ans[2])

def main():
solve()

if __name__ == '__main__':
main()


### 题目描述

#### 样例

##### 输入样例1
2 4 2

##### 输出样例1
3

##### 输入样例2
1 4 3

##### 输出样例2
-1


### 算法1

#### C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e6 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 998244353;

int n, m, k;
int primes[N], cnt;
bool st[N];

inline void init(int n)
{
st[1] = true;
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j=0;i<=n/primes[j];j++)
{
st[i*primes[j]] = true;
if(i%primes[j]==0) break;
}
}
}

inline void solve()
{
auto check = [&](int mid)
{
int tmp = 0;
for(int i=n;i<=n+mid-1;i++)
if(!st[i]) tmp ++;
for(int i=n,j=n+mid-1;j<=m;i++,j++)
{
if(tmp<k) return false;
if(!st[i]) tmp --;
if(!st[j+1]) tmp ++;
}
return true;
};

cin>>n>>m>>k;
int l = 0, r = m - n + 1;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(check(r)) cout<<r<<endl;
else cout<<-1<<endl;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

init(N - 1);

solve();

return 0;
}


#### Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

public static int N = 1000005, M = N * 2, INF = 0x3f3f3f3f;

public static void solve()
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
boolean[] st = new boolean[m + 10];
int[] primes = new int[m + 10];
int cnt = 0;
st[1] = true;
for(int i = 2; i <= m; i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0; i <= m / primes[j]; j++)
{
st[i * primes[j]] = true;
if(i % primes[j] == 0) break;
}
}
int tmp = 0;
for(int i = n; i <= m; i++)
if(!st[i]) tmp++;
if(tmp < k) System.out.println(-1);
else{
int l = 0, r = m - n + 1;
while(l < r)
{
int mid = l + r >> 1;
boolean flag = true;
tmp = 0;
for(int i=n;i<=n+mid-1;i++)
if(!st[i]) tmp ++;
for(int i=n,j=n+mid-1;j<=m;i++,j++)
{
if(tmp<k){
flag = false;
break;
}
if(!st[i]) tmp --;
if(!st[j+1]) tmp ++;
}
if(flag) r = mid;
else l = mid + 1;
}
System.out.println(r);
}
}

public static void main(String[] args)
{
solve();
}
}


#### Python 代码

#  https://www.acwing.com/blog/content/34755/

st = [0] * (1000011)
primes = [0] * (1000011)

def init(n:int):
st[1] = True
cnt = 0
for i in range(2, n + 1):
if st[i] == False:
primes[cnt] = i
cnt += 1
j = 0
while i <= n / primes[j]:
st[i * primes[j]] = True
if i % primes[j] == 0:
break
j += 1

def check(mid:int, n:int, m:int, k:int) -> bool:
tmp = 0
for i in range(n, n + mid):
if st[i] == False: tmp += 1
i = n
for j in range(n + mid - 1, m + 1):
if tmp < k: return False
if st[i] == False: tmp -= 1
if st[j+1] == False: tmp += 1
i += 1
return True

def solve():
n, m, k = map(int, input().split())

init(m + 10)

l, r = 0, m - n + 1
while l < r:
mid = l + r >> 1
if check(mid, n, m, k):
r = mid
else:
l = mid + 1

if check(r, n, m, k):
print(r)
else:
print(-1)

def main():
solve()

if __name__ == '__main__':
main()


### 算法2

#### C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e6 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 998244353;

int n, m, k;
int primes[N], cnt;
bool st[N];

inline void init(int n)
{
st[1] = true;
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j=0;i<=n/primes[j];j++)
{
st[i*primes[j]] = true;
if(i%primes[j]==0) break;
}
}
}

inline void solve()
{
cin>>n>>m>>k;

int tmp = 0;
for(int i=n;i<=m;i++)
if(!st[i]) tmp++;
if(tmp<k) cout<<-1<<endl;
else{
int res = 0, tmp = !st[n];
for(int i=n,j=n+1;;i++){
while(tmp<k && j<=m){
if(!st[j++]) tmp++;
}
if(tmp<k){
res = max(res, j - i + 1);
break;
}
res = max(res, j - i);
if(!st[i]) tmp--;
if(j>m) break;
}
cout<<res<<endl;
}
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

init(N - 1);

solve();

return 0;
}


#### Java 代码

//  https://www.acwing.com/blog/content/34755/

import java.util.*;

public class Main{

public static int N = 200005, M = N * 2, INF = 0x3f3f3f3f;

public static void solve()
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
boolean[] st = new boolean[m + 10];
int[] primes = new int[m + 10];
int cnt = 0;
st[1] = true;
for(int i = 2; i <= m; i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0; i <= m / primes[j]; j++)
{
st[i * primes[j]] = true;
if(i % primes[j] == 0) break;
}
}
int tmp = 0;
for(int i = n; i <= m; i++)
if(!st[i]) tmp++;
if(tmp < k) System.out.println(-1);
else{
int res = 0;
if(st[n] == false) tmp = 1;
else tmp = 0;
for(int i=n,j=n+1;;i++){
while(tmp<k && j<=m){
if(!st[j++]) tmp++;
}
if(tmp<k){
res = Math.max(res, j - i + 1);
break;
}
res = Math.max(res, j - i);
if(!st[i]) tmp--;
if(j>m) break;
}
System.out.println(res);
}
}

public static void main(String[] args)
{
solve();
}
}


#### Python 代码

#  https://www.acwing.com/blog/content/34755/

st = [0] * (1000011)
primes = [0] * (1000011)

def init(n:int):
st[1] = True
cnt = 0
for i in range(2, n + 1):
if st[i] == False:
primes[cnt] = i
cnt += 1
j = 0
while i <= n / primes[j]:
st[i * primes[j]] = True
if i % primes[j] == 0:
break
j += 1

def solve():
n, m, k = map(int, input().split())

init(m + 10)

tmp = 0;
for i in range(n, m + 1):
if st[i] == False: tmp += 1

if tmp < k: print(-1)
else:
res, tmp = 0, st[n] == False
j = n + 1
for i in range(n, m + 1):
while tmp<k and j<=m:
if st[j] == False: tmp += 1
j += 1

if tmp < k:
res = max(res, j - i + 1)
break

res = max(res, j - i)
if st[i] == False: tmp -= 1
if j > m: break

print(res)

def main():
solve()

if __name__ == '__main__':
main()