Lucien

Codeforces 1076B - Divisor Subtraction
Codeforces 1076B - Divisor Subtraction题解链接https://lucien....

22
2018/12

Codeforces 1076B - Divisor Subtraction

题解链接

https://lucien.ink

题目链接

http://codeforces.com/contest/1076/problem/B

题意

1. 如果 $n = 0$ 结束程序
2. 找到 $n$ 的最小质因数 $d$
3. $n = n - d$ ，然后回到步骤 $1$

实现

https://pasteme.cn/2740

#include <bits/stdc++.h>
const int maxn = int(1e5) + 7;
long long n;
bool prime[maxn];
bool isprime(long long x) {
for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false;
return true;
}
int main() {
#ifdef AC
freopen("../in", "r", stdin);
#endif
memset(prime, true, sizeof(prime));
for (int i = 2; i < maxn; i++) {
if (!prime[i]) continue;
for (int j = i + i; j < maxn; j += i) prime[j] = false;
}
scanf("%lld", &n);
long long ans = n;
if (ans & 1) {
if (isprime(ans)) return 0 * puts("1");
for (int i = 3; i <= ans; i++) {
if (ans % i == 0 && prime[i]) {
ans -= i;
break;
}
}
}
printf("%lld\n", ans / 2 + (n & 1));
return 0;
}
Last modification：December 22nd, 2018 at 05:24 pm