Zlc晨鑫

6294

Screaming
yxc的小迷妹

_____Xyz__
yxᴄ
Moon_2
18910310021

StarLi9ht
heart

rfx

jixiaobai

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int cnt[N], s[N];
int n, a[N];

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

for (int i = 1; i <= n; i ++ ) cnt[a[i]] ++ ;

for (int i = 1; i < N; i ++ )
for (int j = i; j < N; j += i)
s[j] += cnt[i];

for (int i = 1; i <= n; i ++ )
printf("%d\n", s[a[i]] - 1);

return 0;
}


### T1

$ans2 = ans - t, t = w[j] - w[i]$。

### T2

#include <cstdio>
#include <iostream>

using namespace std;

#define int long long

const int mod = 100003;

int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}

signed main()
{
int m, n;
cin >> m >> n;
int ans = qmi(m, n, mod) - m * qmi(m - 1, n - 1, mod);
cout << (ans % mod + mod) % mod << endl;
return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

#define int long long

const int mod = 200907;

int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}

signed main()
{
int T;
cin >> T;
while (T -- )
{
int a, b, c, k;
cin >> a >> b >> c >> k;
if (b - a == c - b) cout << (a + (b - a) * (k - 1)) % mod << endl;
else cout << a * qmi(b / a, k - 1, mod) % mod << endl;
}
return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1000010;

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

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

int main()
{
int n;
cin >> n;
get_primes(n);
for (int i = 0; i < cnt; i ++ )
{
int s = 0, p = primes[i];
for (int j = n; j; j /= p) s += j / p;
printf("%d %d\n", p, s);
}
return 0;
}


#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

#define int long long

const int N = 1e6 + 10;

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

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

signed main()
{
int l, r;
while (scanf("%lld%lld", &l, &r) == 2)
{
init(50000);
memset(st, 0, sizeof st);
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
for (int j = max((int)ceil(l / p) * p, 2 * p); j <= r; j += p)
if (j >= l) st[j - l] = true;
}

cnt = 0;
// 注意1不是质数
for (int i = 0; i <= r - l; i ++ )
if (!st[i] && i + l >= 2) primes[cnt ++ ] = i + l;

if (cnt < 2)
{
continue;
}

int p1, p2;
p1 = p2 = 0;
for (int i = 0; i + 1 < cnt; i ++ )
{
int v = primes[i + 1] - primes[i];
if (v < primes[p1 + 1] - primes[p1]) p1 = i;
if (v > primes[p2 + 1] - primes[p2]) p2 = i;
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n", primes[p1], primes[p1 + 1], primes[p2], primes[p2 + 1]);
}
return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100010;

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

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

int main()
{
int n;
scanf("%d", &n);
get_primes(n + 1);
if (n <= 3) puts("1");
else puts("2");
for (int i = 2; i <= n + 1; i ++ )
if (!st[i]) printf("1 ");
else printf("2 ");
return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

int n, m, k;
int w[N][N], minv[N][N], maxv[N][N], buf[N];
int minx[N], maxx[N];
int q[N];

void get_min(int a[], int b[], int n)
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
{
while (hh <= tt && q[hh] <= i - k) hh ++ ;
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
q[ ++ tt] = i;
b[i] = a[q[hh]];
}
}

void get_max(int a[], int b[], int n)
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
{
while (hh <= tt && q[hh] <= i - k) hh ++ ;
while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
q[ ++ tt] = i;
b[i] = a[q[hh]];
}
}

int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &w[i][j]);

for (int i = 1; i <= n; i ++ )
{
get_min(w[i], minv[i], m);
get_max(w[i], maxv[i], m);
}

int ans = 2e9;
// 注意k之前的数都是没有意义的，它们并不是窗口内真实的最大最小值
// 统计了会WA，因为可能差值会更小
for (int j = k; j <= m; j ++ )
{
for (int i = 1; i <= n; i ++ ) buf[i] = minv[i][j];
get_min(buf, minx, n);
for (int i = 1; i <= n; i ++ ) buf[i] = maxv[i][j];
get_max(buf, maxx, n);
for (int i = k; i <= n; i ++ )
ans = min(ans, maxx[i] - minx[i]);
}

printf("%d\n", ans);

return 0;
}


#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL s[N];
int e[N], n, m;
int q[N];
LL f[N];

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &e[i]);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + e[i];

int hh = 0, tt = -1;
f[0] = 0;
f[1] = s[1];
tt = 0, q[0] = 1;
for (int i = 2; i <= n; i ++ )
{
if (q[hh] <= i - m) hh ++ ;
while (hh <= tt && -s[q[tt]-1]+f[q[tt]-2]<=-s[i-1]+f[i-2]) tt -- ;
q[ ++ tt] = i;
f[i] = -s[q[hh] - 1] + f[q[hh] - 2] + s[i];
f[i] = max(f[i], f[i - 1]);
}

printf("%lld\n", f[n]);

return 0;
}

/*

*/

#include <cstdio>
#include <iostream>

using namespace std;

#define int long long

const int N = 100010;

int n, k;
int e[N], f[N];
int q[N];

signed main()
{
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &e[i]);

int hh = 0, tt = -1;
q[ ++ tt] = 0;
for (int i = 1; i <= n; i ++ )
{
// [i - k - 1, i - 1]
while (hh <= tt && q[hh] < i - k - 1) hh ++ ;
f[i] = f[q[hh]] + e[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
q[ ++ tt] = i;
}

int res = 9e18;
for (int i = n - k; i <= n; i ++ )
res = min(res, f[i]);
res = -res;
for (int i = 1; i <= n; i ++ )
res += e[i];
printf("%lld\n", res);

return 0;
}


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

using namespace std;

const int N = 50010;

int a[N], n, t, f[N];

bool check(int len)
{
static int q[N];
int hh = 0, tt = -1;
q[ ++ tt] = 0;

for (int i = 1; i <= n; i ++ )
{
if (q[hh] < i - len) hh ++ ;
f[i] = f[q[hh]] + a[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
q[ ++ tt] = i;
}

// 注意：只要f[n-len+1,n]之间有一个满足要求即可
for (int i = n - len + 1; i <= n; i ++ )
if (f[i] <= t) return true;
return false;
}

int main()
{
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

int l = 0, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid + 1)) r = mid;
else l = mid + 1;
}

printf("%d\n", r);

return 0;
}



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

using namespace std;

const int N = 50010;

int n, t;
int a[N], q[N], f[N];

bool check(int mid)
{
memset(f, 0, sizeof f);
int hh = 0, tt = -1;
q[ ++ tt] = 0;
for (int i = 1; i <= n; i ++ )
{
// [i-1-mid, i-1]
// 空着的长度最大是mid
while (hh <= tt && q[hh] < i - mid - 1) hh ++ ;
f[i] = f[q[hh]] + a[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
q[ ++ tt] = i;
}

int res = 2e9;
for (int i = n - mid; i <= n; i ++ )
res = min(res, f[i]);

return res <= t;
}

int main()
{
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
int l = 0, r = n; // 可能全部都可以写完
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}