• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解）

2周前 (04-07) 4次浏览

## A – Don’t be late

(cout << (d / s <= t ? “Yes” : “No”);)

## B – Substring

``````int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
int ans = m;
for (int start = 0; start <= n - m; ++start) {
int cnt = 0;
for (int i = 0; i < m; ++i)
if (t[i] != s[start + i]) cnt++;
ans = min(ans, cnt);
}
cout << ans << "n";
return 0;
}
``````

## C – Sum of product of pairs

``````using ll = long long;
const ll mod = 1e9 + 7;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
ll a[n + 1], lst[n + 2] = {};
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = n; i >= 1; --i) {
lst[i] = (lst[i + 1] % mod + (i == n ? 0 : a[i + 1]) % mod) % mod;
}
ll ans = 0;
for (int i = 1; i < n; ++i) {
ans = (ans + a[i] * lst[i] + mod) % mod;
}
cout << ans % mod << "n";
return 0;
}
``````

## D – Friends

• (mathcal{O}(NlogN))
``````const int N = 2e5 + 7;
int f[N], Siz[N];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x != y)
f[x] = y, Siz[y] += Siz[x];
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n, m;
for (int i = 1; i <= N - 1; ++i) f[i] = i, Siz[i] = 1;
cin >> n >> m;
while (m--) {
int x, y;
cin >> x >> y;
merge(x, y);
}
sort(Siz, Siz + n + 1);
cout << Siz[n];
return 0;
}
``````

## E – Coprime

``````int cnt[1 << 20];
int all = 0;
bool isp[1 << 20];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
for (int i = 0, x; i < n; ++i) {
cin >> x;
cnt[x]++;
all = gcd(all, x);
}
bool f = true;
for (int i = 2; i < (1 << 20); ++i) {
int sum = 0;
for (int j = i; j < (1 << 20); j += i) sum += cnt[j];
if (sum > 1) f = false;
}
cout << (f ? "pairwise coprime" : all == 1 ? "setwise coprime"
: "not coprime");
return 0;
}
``````

AtCoder Beginner Contest 177