2889

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
while (cin >> a[n]) n++;
int res = 0;
for (int i = 0; i < n; i++)
{
f[i] = 1;
for (int j = 0; j < i; j++)
if (a[i] <= a[j])   f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
int cnt = 0;
for (int i = 0; i < n; i++)
{
g[i] = 1;
for (int j = 0; j < i; j++)
if (a[i] > a[j])   g[i] = max(g[i], g[j] + 1);
cnt = max(cnt, g[i]);
}
cout << res << endl << cnt << endl;
return 0;
}


#include<iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

const int N = 1000010;
int primes[N], cnt;
bool st[N];
unordered_set<int> isp;

void get_primes(int n)
{
for (int i = 2; i <= n; i++){
if (!st[i]) primes[cnt++] = i, isp.insert(i);
for (int j = 0; primes[j] <= n / i; j++){
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
get_primes(N);
int n;
while (cin >> n, n){
for (int i = 0; i < cnt; i++){
if (isp.count(n - primes[i])){
printf("%d = %d + %d\n", n, primes[i], n - primes[i]);
break;
}
}
}
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N];

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int res = -1;
for (int i = 0; i < n; i++){
f[i] = a[i];
for (int j = 0; j < n; j++)
if (a[i] > a[j])    f[i] = max(f[i], f[j] + a[i]);
res = max(res, f[i]);
}
cout << res;
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

PII h[N];
int f[N];

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> h[i].first >> h[i].second;
sort(h, h + n);

int res = -1;
for (int i = 0; i < n; i++)
{
f[i] = 1;
for (int j = 0; j < i; j++)
if (h[i].second > h[j].second)
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
cout << res;

return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 300;
int a[N], g[N], f[N];

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];

for (int i = 0; i < n; i++){
f[i] = 1;
for (int j = 0; j < i; j++)
if (a[i] > a[j])    f[i] = max(f[i], f[j] + 1);
}

for (int i = n - 1; i >= 0; i--){
g[i] = 1;
for (int j = n - 1; j > i; j--)
if (a[i] > a[j])    g[i] = max(g[i], g[j] + 1);
}

int res = N;
for (int i = 0; i < n; i++){
res = min(res, n - (f[i] + g[i] - 1));
}
cout << res;
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N], g[N];

int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];

for (int i = 0; i < n; i++)
{
f[i] = 1;
for (int j = 0; j < i; j++)
if (a[i] > a[j])    f[i] = max(f[i], f[j] + 1);
}

for (int i = n - 1; i >= 0; i--)
{
g[i] = 1;
for (int j = n - 1; j > i; j--)
if (a[i] > a[j])    g[i] = max(g[i], g[j] + 1);
}

int res = 0;

for (int i = 0; i < n; i++) res = max(res, f[i] + g[i] - 1);

cout << res;

return 0;
}


int n;
int a[N];

int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];

vector<int> q;
for (int i = 0; i < n; i++)
{
if (!i || a[i] > q.back())  q.push_back(a[i]);
else    *lower_bound(q.begin(), q.end(), a[i]) = a[i];
}
cout << q.size();
return 0;
}


# include[HTML_REMOVED]

using namespace std;

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n;
cin >> n;
while (n–)
{
int x, y;
cin >> x >> y;
cout << gcd(x, y) << endl;
}
return 0;
}

#include<iostream>
#include<unordered_map>

using namespace std;

const int N = 1e9 + 7;

unordered_map<int, int> primes;

void get(int x)
{
for (int i = 2; i <= x / i; i++)
while (x % i == 0)
{
x /= i;
primes[i]++;
}
if (x != 1) primes[x]++;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
get(x);
}
long long res = 1;
for (auto prime : primes)
{
int p = prime.first, a = prime.second;
long long t = 1;
while (a--) t = (t * p + 1) % N;
res = res * t % N;
}
cout << res;

return 0;
}


算术基本定理，一个数可以表示为：
$$N = p_1^{\alpha1} \times p_2^{\alpha2} \times p_3^{\alpha3} \times \cdots \times p_k^{\alpha k}$$

$$d = p_1^{\beta1} \times p_2^{\beta2} \times p_3^{\beta3} \times \cdots \times p_k^{\beta k} , 0 \le \beta_i \le \alpha_i$$