题单:https://codeforces.com/problemset/page/1?tags=number%20theory,1601-1900
原题指路:https://codeforces.com/problemset/problem/294/C
n n n盏灯排成一行,从左到右依次编号 1 ∼ n 1\sim n 1∼n,初始时有些灯亮有些灯灭.每一步可点亮个灭了的灯,如果它两边至少有一个亮的灯.问有多少种使得灯全亮的开灯方案,答案对 1 e 9 + 7 1\mathrm{e}9+7 1e9+7取模.
第一行输入两个整数 n , m ( 1 ≤ m ≤ n ≤ 1000 ) n,m\ \ (1\leq m\leq n\leq 1000) n,m (1≤m≤n≤1000),分别表示灯的个数和初始时亮的灯的个数.第二行输入 n n n个范围为 [ 1 , n ] [1,n] [1,n]的整数,表示初始时亮的灯的编号.
m m m个亮的灯将序列分为 ( m + 1 ) (m+1) (m+1)段,从左往右编号 1 ∼ ( m + 1 ) 1\sim (m+1) 1∼(m+1).每次操作只能点亮每一段内的最左边或最右边的灯,特别地,第一段只能点亮最右边的灯,最后一段只能点亮最左边的灯.
设第 i ( 1 ≤ i ≤ m + 1 ) i\ \ (1\leq i\leq m+1) i (1≤i≤m+1)段的长度为 l e n i len_i leni,先只考虑每次点亮的是哪一段内的灯,有 ( n − m ) ! ∏ i = 1 m + 1 l e n i ! \dfrac{(n-m)!}{\displaystyle\prod_{i=1}^{m+1} len_i!} i=1∏m+1leni!(n−m)!种情况.
考虑每次点亮每一段内的最左边还是最右边的灯,第 i i i段中前 ( l i − 1 ) (l_i-1) (li−1)个灯都有两种选择,最后一个灯只有一种选择,故 a n s = ( n − m ) ! ∏ i = 1 m + 1 l e n i ! ⋅ ∏ i = 1 m + 1 2 l e n i − 1 \displaystyle ans=\dfrac{(n-m)!}{\displaystyle\prod_{i=1}^{m+1} len_i!}\cdot \prod_{i=1}^{m+1} 2^{len_i-1} ans=i=1∏m+1leni!(n−m)!⋅i=1∏m+12leni−1.
const int MAXN = 1005;
const int MOD = 1e9 + 7;
int n, m;
int pos[MAXN];
int fac[MAXN], ifac[MAXN];
int pow2[MAXN];
void init() {
fac[0] = 1;
for (int i = 1; i < MAXN; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2, MOD);
for (int i = MAXN - 1; i; i--) ifac[i - 1] = (ll)ifac[i] * i % MOD;
pow2[0] = 1;
for (int i = 1; i < MAXN; i++) pow2[i] = (ll)pow2[i - 1] * 2 % MOD;
}
void solve() {
init();
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> pos[i];
sort(pos + 1, pos + m + 1);
pos[m + 1] = n + 1; // 哨兵,减少特判边界
int ans = fac[n - m];
for (int i = 0; i <= m; i++) {
int len = pos[i + 1] - pos[i] - 1;
if (len <= 0) continue;
if (i > 0 && i < m) // 注意pos[i]和pos[i+1]都在范围内时才需要乘2的幂次
ans = (ll)ans * pow2[len - 1] % MOD;
ans = (ll)ans * ifac[len] % MOD;
}
cout << ans;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/336/C
一个集合 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an的权值定义为最大的非负整数 v s . t . 2 v ∣ ( a 1 & ⋯ & a n ) v\ s.t.\ 2^v\mid (a_1\&\cdots\& a_n) v s.t. 2v∣(a1&⋯&an),若这样的非负整数 v v v不存在,定义该集合的权值为 − 1 -1 −1.给定 n n n个整数 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an,从中选出 k k k个相异的整数$b_1,\cdots,b_k\ s.t.\ 它们的构成的集合权值最大 . 若有多组解 , 输出 它们的构成的集合权值最大.若有多组解,输出 它们的构成的集合权值最大.若有多组解,输出k$最大的任一组.
第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n (1≤n≤1e5).第二行输入 n n n个整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1,⋯,an (1≤ai≤1e9).
x % y ≤ min { x , y } x\% y\leq \min\{x,y\} x%y≤min{x,y},从高到低枚举 v v v,将所有二进制第 v v v位为 1 1 1的元素存下来,检查它们相与后能否被 2 v 2^v 2v整除即可.枚举完所有 v v v即无解.
void solve() {
int n; cin >> n;
vi a(n);
for (auto& ai : a) cin >> ai;
vi ans;
for (int v = 30; v >= 0; v--) {
ans.clear();
int tmp = 0x3fffffff; // 选出来的数相与的结果
for (auto ai : a) {
if (ai >> v & 1) {
ans.push_back(ai);
tmp &= ai;
}
}
if (ans.size() && tmp % (1 << v) == 0) {
cout << ans.size() << endl;
for (auto i : ans) cout << i << ' ';
return;
}
}
cout << -1;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/359/C
给定一个素数 x ( 2 ≤ x ≤ 1 e 9 ) x\ \ (2\leq x\leq 1\mathrm{e}9) x (2≤x≤1e9)和 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n (1≤n≤1e5)个非负整数 a 1 , ⋯ , a n ( 0 ≤ a 1 ≤ ⋯ ≤ a n ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (0\leq a_1\leq \cdots\leq a_n\leq 1\mathrm{e}9) a1,⋯,an (0≤a1≤⋯≤an≤1e9).设 1 x a 1 + ⋯ + 1 x a n = s t \dfrac{1}{x^{a_1}}+\cdots+\dfrac{1}{x^{a_n}}=\dfrac{s}{t} xa11+⋯+xan1=ts,其中 t = x a 1 + ⋯ + a n t=x^{a_1+\cdots+a_n} t=xa1+⋯+an.求 gcd ( s , t ) \gcd(s,t) gcd(s,t),答案对 1 e 9 + 7 1\mathrm{e}9+7 1e9+7取模.
设 s u m = a 1 + ⋯ + a n sum=a_1+\cdots+a_n sum=a1+⋯+an,则 s = x s u m − a 1 + ⋯ + x s u m − a n s=x^{sum-a_1}+\cdots+x^{sum-a_n} s=xsum−a1+⋯+xsum−an.显然 a n s = x k ( k ∈ Z ) ans=x^k\ \ (k\in\mathbb{Z}) ans=xk (k∈Z).
下面求 k k k.
设 b i = s u m − a i b_i=sum-a_i bi=sum−ai,则 b 1 ≥ ⋯ ≥ b n b_1\geq\cdots\geq b_n b1≥⋯≥bn.每次取出 b [ ] b[] b[]中最小的元素 v v v,统计 b [ ] b[] b[]中值为 v v v的元素个数 c n t cnt cnt.
①若 c n t cnt cnt不是 x x x的倍数,则 a n s = x min { v , s u m } ans=x^{\min\{v,sum\}} ans=xmin{v,sum}.
②若 c n t cnt cnt是 x x x的倍数,则此时的 v v v可能仍不是答案,在 b [ ] b[] b[]末尾加入 c n t x \dfrac{cnt}{x} xcnt个 ( v + 1 ) (v+1) (v+1).重复上述过程
const int MOD = 1e9 + 7;
void solve() {
int n, x; cin >> n >> x;
vi a(n);
ll sum = 0; // a[]的元素之和
for (auto& ai : a) {
cin >> ai;
sum += ai;
}
vl b(n);
for (int i = 0; i < n; i++) b[i] = sum - a[i];
while (true) {
ll v = b.back();
int cnt = 0; // b[]中值为v的数的个数
while (b.size() && b.back() == v) {
cnt++;
b.pop_back();
}
if (cnt % x) {
cout << qpow(x, min(v, sum), MOD);
return;
}
else {
cnt /= x;
while (cnt--) b.push_back(v + 1);
}
}
}
int main() {
solve();
}
设 s s s和 t t t的 x x x进制表示中末尾连续 0 0 0的个数分别为 c 1 c_1 c1和 c 2 c_2 c2,则 gcd ( s , t ) = x min { c 1 , c 2 } \gcd(s,t)=x^{\min\{c_1,c_2\}} gcd(s,t)=xmin{c1,c2}.
用一个map来模拟将每个 ( s u m − a i ) (sum-a_i) (sum−ai)转成 x x x进制数的过程即可.
const int MOD = 1e9 + 7;
int n, x;
map<ll, int> cnt; // 记录每个(sum - a[i])出现的次数
void solve() {
cin >> n >> x;
vi a(n);
ll sum = 0; // a[]的元素之和
for (auto& ai : a) {
cin >> ai;
sum += ai;
}
for (auto ai : a) cnt[sum - ai]++;
for (auto& [u, v] : cnt) // 注意取引用
if (v >= x) cnt[u + 1] += v / x, v %= x; // 处理x进制的进位
for (auto [u, v] : cnt) {
if (v) {
cout << qpow(x, min(sum, u), MOD);
return;
}
}
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/385/C
给定一个长度为 n n n的序列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an和 m m m个询问.每个询问给定两个整数 l , r l,r l,r,求 ∑ p ∈ S ( l , r ) f ( p ) \displaystyle \sum_{p\in S(l,r)} f(p) p∈S(l,r)∑f(p),其中 S ( l , r ) S(l,r) S(l,r)表示 [ l , r ] [l,r] [l,r]范围内的素数, f ( p ) f(p) f(p)表示使得 p ∣ a k ( l ≤ k ≤ r ) p\mid a_k\ \ (l\leq k\leq r) p∣ak (l≤k≤r)的下标 k k k的个数.
第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 6 ) n\ \ (1\leq n\leq 1\mathrm{e}6) n (1≤n≤1e6).第二行输入 n n n个整数 a 1 , ⋯ , a n ( 2 ≤ a i ≤ 1 e 7 ) a_1,\cdots,a_n\ \ (2\leq a_i\leq 1\mathrm{e}7) a1,⋯,an (2≤ai≤1e7).第三行输入一个整数 m ( 1 ≤ m ≤ 5 e 4 ) m\ \ (1\leq m\leq 5\mathrm{e}4) m (1≤m≤5e4),表示询问次数.接下来 m m m行每行输入两个整数 l , r ( 2 ≤ l ≤ r ≤ 2 e 9 ) l,r\ \ (2\leq l\leq r\leq 2\mathrm{e}9) l,r (2≤l≤r≤2e9).
因 a ≤ 1 e 7 a\leq 1\mathrm{e}7 a≤1e7,则只需考虑 1 e 7 1\mathrm{e}7 1e7内的素数对答案的贡献,换句话说,只需对每个 1 e 7 1\mathrm{e}7 1e7内的素数 p p p,求 f ( p ) f(p) f(p).
考虑如何求 f ( p ) f(p) f(p).设 c n t [ x ] cnt[x] cnt[x]表示 a [ ] a[] a[]中元素 x x x出现的次数.
① f ( 2 ) = c n t [ 1 ⋅ 2 ] + c n t [ 2 ⋅ 2 ] + ⋯ f(2)=cnt[1\cdot 2]+cnt[2\cdot 2]+\cdots f(2)=cnt[1⋅2]+cnt[2⋅2]+⋯.
② f ( 3 ) = c n t [ 1 ⋅ 3 ] + c n t [ 2 ⋅ 3 ] + ⋯ f(3)=cnt[1\cdot 3]+cnt[2\cdot 3]+\cdots f(3)=cnt[1⋅3]+cnt[2⋅3]+⋯.
③ f ( p ) = c n t [ 1 ⋅ p ] + c n t [ 2 ⋅ p ] + ⋯ f(p)=cnt[1\cdot p]+cnt[2\cdot p]+\cdots f(p)=cnt[1⋅p]+cnt[2⋅p]+⋯.
显然上述过程类似于埃氏筛,可在埃氏筛筛素数的过程中预处理出 f ( p ) f(p) f(p).
求 f ( p ) f(p) f(p)的前缀和数组 p r e [ ] pre[] pre[],对每个询问 [ l , r ] [l,r] [l,r],二分出在范围 [ l , r ] [l,r] [l,r]内的最小、最大的素数在素数数组 p r i m e s [ ] primes[] primes[]中的下标 L , R L,R L,R,则 a n s = p r e [ r ] − p r e [ l − 1 ] ans=pre[r]-pre[l-1] ans=pre[r]−pre[l−1].注意 l , r l,r l,r可能超过 1 e 7 1\mathrm{e}7 1e7,而超过 1 e 7 1\mathrm{e}7 1e7的部分对答案无贡献,故 l > 1 e 7 l>1\mathrm{e}7 l>1e7内最大的素数时直接返回 0 0 0即可.
const int MAXN = 1e7 + 5;
int n;
int mp[MAXN]; // mp[x]表示a[]中值为x的数的个数
int primes[MAXN], cnt;
bool state[MAXN];
int f[MAXN]; // f[]的前缀和数组
void init() { // 预处理f[]
for (int i = 2; i < MAXN; i++) {
if (!state[i]) primes[cnt++] = i;
for (int j = 0; (ll)primes[j] * i < MAXN; j++) {
state[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
for (int i = 0; i < cnt; i++) {
for (int j = 1; (ll)primes[i] * j < MAXN; j++)
f[i] += mp[primes[i] * j];
f[i] += f[i - 1]; // 求前缀和
}
}
void solve() {
cin >> n;
while (n--) {
int a; cin >> a;
mp[a]++;
}
init();
CaseT{
int l, r; cin >> l >> r;
if (l > primes[cnt - 1]) {
cout << 0 << endl;
continue;
}
int L = lower_bound(primes, primes + cnt, l) - primes;
int R = upper_bound(primes, primes + cnt, r) - primes - 1;
cout << f[R] - f[L - 1] << endl;
}
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/402/D
给定一个长度为 n n n的整数序列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an和一个坏素数的集合 b 1 , ⋯ , b m b_1,\cdots,b_m b1,⋯,bm.未出现在 b [ ] b[] b[]中的素数称为好素数.定义序列 a [ ] a[] a[]的权值未 ∑ i = 1 n f ( a i ) \displaystyle \sum_{i=1}^n f(a_i) i=1∑nf(ai),其中 f ( s ) f(s) f(s)定义如下:① f ( 1 ) = 0 f(1)=0 f(1)=0;②设 p p p是 s s s的最小素因子.若 p p p是好素数, f ( s ) = f ( s p ) + 1 f(s)=f\left(\dfrac{s}{p}\right)+1 f(s)=f(ps)+1;否则 f ( s ) = f ( s p ) − 1 f(s)=f\left(\dfrac{s}{p}\right)-1 f(s)=f(ps)−1.现有操作:选择一个下标 r ( 1 ≤ r ≤ n ) r\ \ (1\leq r\leq n) r (1≤r≤n),设 g = gcd ( a 1 , ⋯ , a r ) g=\gcd(a_1,\cdots,a_r) g=gcd(a1,⋯,ar),令 a 1 / = g , ⋯ , a r / = g a_1/=g,\cdots,a_r/=g a1/=g,⋯,ar/=g.问进行若干次(可能为零次)操作后序列 a [ ] a[] a[]的最大权值.
第一行输入两个整数 n , m ( 1 ≤ n , m ≤ 5000 ) n,m\ \ (1\leq n,m\leq 5000) n,m (1≤n,m≤5000).第二行输入 n n n个整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1,⋯,an (1≤ai≤1e9).第三行输入 m m m个整数 b 1 , ⋯ , b m ( 2 ≤ b 1 < ⋯ < b m ≤ 1 e 9 ) b_1,\cdots,b_m\ \ (2\leq b_1<\cdots<b_m\leq 1\mathrm{e}9) b1,⋯,bm (2≤b1<⋯<bm≤1e9).
注意到前缀 gcd \gcd gcd p r e r = gcd 1 ≤ i ≤ r a i \displaystyle pre_r=\gcd_{1\leq i\leq r} a_i prer=1≤i≤rgcdai随 r r r的增大不增,且对 ∀ r ′ < r \forall r'<r ∀r′<r, p r e r pre_{r} prer的素因子是 p r e r ′ pre_{r'} prer′的素因子的子集.若从前往后考虑每个操作,对每个操作 i ( 1 ≤ i ≤ n ) i\ \ (1\leq i\leq n) i (1≤i≤n),只有第一次操作时才会产生贡献 − i ⋅ f ( gcd ( a 1 , ⋯ , a i ) ) -i\cdot f(\gcd(a_1,\cdots,a_i)) −i⋅f(gcd(a1,⋯,ai)).对每个操作 j ( i < j ≤ n ) j\ \ (i<j\leq n) j (i<j≤n),因操作 i i i使得前 i i i个数互素,则前 j j j个数的 gcd = 1 \gcd=1 gcd=1,不再对答案有贡献.故从前往后考虑每个操作相当于只进行了第一次操作.
从后往前考虑每个操作,设当前操作为 i i i,上一操作为 j j j,则当前位置剩余的最小素因子的集合等于 gcd ( a 1 , ⋯ , a i ) \gcd(a_1,\cdots,a_i) gcd(a1,⋯,ai)的素因子构成的集合与 gcd ( a 1 , ⋯ , a j ) \gcd(a_1,\cdots,a_j) gcd(a1,⋯,aj)的素因子构成的集合的差集,但这不方便统计答案.从前往后考察上述过程,因前缀 gcd \gcd gcd不增,则前面的操作不会影响当前位置剩余的素因子的集合,只影响每个素因子的贡献的倍数.设当前操作为 i i i,上一操作为 j j j,则操作 i i i对答案的贡献为 − ( i − j ) ⋅ f ( gcd ( a 1 , ⋯ , a i ) ) -(i-j)\cdot f(\gcd(a_1,\cdots,a_i)) −(i−j)⋅f(gcd(a1,⋯,ai)).
d p [ i ] dp[i] dp[i]表示操作完前 i i i个数后增加的分数的最大值,则 a n s = ∑ i = 1 n f ( a i ) + d p n \displaystyle ans=\sum_{i=1}^n f(a_i)+dp_n ans=i=1∑nf(ai)+dpn.
状态转移方程 d p [ i ] = max 0 ≤ j < i { d p [ j ] − ( i − j ) ⋅ f ( p r e [ i ] ) } \displaystyle dp[i]=\max_{0\leq j<i}\left\{dp[j]-(i-j)\cdot f(pre[i])\right\} dp[i]=0≤j<imax{dp[j]−(i−j)⋅f(pre[i])}.
只需预处理 1 e 9 \sqrt{1\mathrm{e}9} 1e9 内的素数.
const int MAXN = 1e5 + 5;
int n, m;
int a[MAXN];
umap<int, bool> bad; // 坏素数
int primes[MAXN], cnt;
bool state[MAXN];
ll dp[MAXN]; // dp[i]表示操作完前i个数后增加的分数的最大值
void init() {
for (int i = 2; i < MAXN; i++) {
if (!state[i]) primes[cnt++] = i;
for (int j = 0; (ll)primes[j] * i < MAXN; j++) {
state[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int f(int x) {
int res = 0;
for (int i = 0; i < cnt && (ll)primes[i] * primes[i] <= x; i++) {
if (x % primes[i] == 0) {
int cnt = 0;
while (x % primes[i] == 0) x /= primes[i], cnt++;
res += (bad[primes[i]] ? -1 : 1) * cnt;
}
}
if (x > 1) res += bad[x] ? -1 : 1;
return res;
}
void solve() {
init();
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
while (m--) {
int b; cin >> b;
bad[b] = true;
}
ll ans = 0;
for (int i = 1; i <= n; i++) ans += f(a[i]); // 初始权值
ll add = 0; // 最大增加分数
int g = 0;
for (int i = 1; i <= n; i++) {
g = gcd(g, a[i]);
int tmp = -f(g);
dp[i] = (ll)i * tmp;
for (int j = 0; j < i; j++)
dp[i] = max(dp[i], dp[j] + (ll)(i - j) * tmp);
add = max(add, dp[i]);
}
cout << ans + add;
}
int main() {
solve();
}
从后往前贪心可以使答案更优的下标 r r r,做操作 r r r并更新答案.
[证] 设最优解中进行操作的下标为 r 1 > ⋯ > r k r_1>\cdots>r_k r1>⋯>rk,贪心进行操作的下标为 l 1 > ⋯ > l m l_1>\cdots>l_m l1>⋯>lm.
① r 1 ≤ l 1 r_1\leq l_1 r1≤l1,这是因为贪心策略保证 > l 1 >l_1 >l1的下标都不能使得答案更优.
② r 1 ≥ l 1 r_1\geq l_1 r1≥l1,若不然,则 r 1 < l 1 r_1<l_1 r1<l1,由前缀 gcd \gcd gcd不增知:进行操作 l 1 l_1 l1能使得答案更优,矛盾.
故 l 1 = r 1 l_1=r_1 l1=r1,由数归知其他也对应相等.
例如,区间 [ 1 , 5 ] [1,5] [1,5]的 gcd = 12 \gcd=12 gcd=12,区间 [ 1 , 9 ] [1,9] [1,9]的 gcd = 4 \gcd=4 gcd=4,则先在下标 9 9 9的位置除以 4 4 4,再在下标 5 5 5的位置除以 3 3 3即可.
const int MAXN = 1e5 + 5;
int n, m;
int a[MAXN];
int pre[MAXN]; // 前缀gcd
umap<int, bool> bad; // 坏素数
int primes[MAXN], cnt;
bool state[MAXN];
void init() {
for (int i = 2; i < MAXN; i++) {
if (!state[i]) primes[cnt++] = i;
for (int j = 0; (ll)primes[j] * i < MAXN; j++) {
state[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int f(int x) {
int res = 0;
for (int i = 0; i < cnt && (ll)primes[i] * primes[i] <= x; i++) {
if (x % primes[i] == 0) {
int cnt = 0;
while (x % primes[i] == 0) x /= primes[i], cnt++;
res += (bad[primes[i]] ? -1 : 1) * cnt;
}
}
if (x > 1) res += bad[x] ? -1 : 1;
return res;
}
void solve() {
init();
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = gcd(pre[i - 1], a[i]);
}
while (m--) {
int b; cin >> b;
bad[b] = true;
}
ll ans = 0;
for (int i = 1; i <= n; i++) ans += f(a[i]); // 初始权值
ll add = 0; // 最大增加分数
int div = 1;
for (int i = n; i >= 1; i--) {
int tmp = f(pre[i] /= div);
if (tmp < 0) ans -= (ll)i * tmp, div *= pre[i];
}
cout << ans + add;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/439/C
给定 n n n个相异的整数 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an,将其划分为 k k k个不相交的非空集合,其中 p p p个集合的元素之和为偶数,另外 ( k − p ) (k-p) (k−p)个集合的元素之和为奇数.若不存在划分方案,则输出"NO";否则第一行输出"YES",之后 k k k行每行输出一个集合的元素.
第一行输入三个整数 n , k , p ( 1 ≤ k ≤ n ≤ 1 e 5 , 0 ≤ p ≤ k ) n,k,p\ \ (1\leq k\leq n\leq 1\mathrm{e}5,0\leq p\leq k) n,k,p (1≤k≤n≤1e5,0≤p≤k).第二行输入 n n n个相异的整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1,⋯,an (1≤ai≤1e9).
有解的条件:
①至少有 ( k − p ) (k-p) (k−p)个奇数,组成 ( k − p ) (k-p) (k−p)个由一个奇数组成的和为奇数的集合,
②奇数的个数与 ( k − p ) (k-p) (k−p)的奇偶性相同.
若不同,如奇数的个数 = k − p + 1 =k-p+1 =k−p+1时,多出来的一个奇数会破坏一个和为奇数或偶数的集合.
③偶数的个数与剩下的奇数的个数的一半之和 ≥ p \geq p ≥p,即组成和为奇数的集合后,多余的奇数两个一组构成和为偶数的集合.
对有解的情况,先构造 ( k − p ) (k-p) (k−p)个和为奇数的集合,多余的奇数两个一组构成和为偶数的集合.将所有偶数一个一组构成和为偶数的集合.先输出构造出来的前 ( k − 1 ) (k-1) (k−1)个集合作为答案,将其余的元素和为一个集合输出.
void print(vi& a) {
cout << a.size() << ' ';
for (auto ai : a) cout << a << ' ';
cout << endl;
}
void solve() {
int n, k, p; cin >> n >> k >> p;
vi even, odd;
while (n--) {
int a; cin >> a;
if (a & 1) odd.push_back(a);
else even.push_back(a);
}
bool ok = true;
vector<vi> ans;
if (odd.size() < k - p) ok = false;
else if ((int)odd.size() %2 != (k - p) % 2) ok = false;
else if (even.size() + (odd.size() - k + p) / 2 < p) ok = false;
else {
for (int i = 0; i < k - p; i++) { // 一个奇数组成一个和为奇数的集合
vi tmp;
tmp.push_back(odd.back()), odd.pop_back();
ans.push_back(tmp);
}
while (odd.size() >= 2) { // 两个奇数组成一个和为偶数的集合
vi tmp;
tmp.push_back(odd.back()), odd.pop_back();
tmp.push_back(odd.back()), odd.pop_back();
ans.push_back(tmp);
}
for (auto i : even) { // 一个偶数组成一个和为偶数的集合
vi tmp;
tmp.push_back(i);
ans.push_back(tmp);
}
}
if (!ok) cout << "NO";
else {
cout << "YES" << endl;
for (int i = 0; i < k - 1; i++) print(ans[i]);
vi rest;
for (int i = k - 1; i < ans.size(); i++)
for (auto j : ans[i]) rest.push_back(j);
print(rest);
}
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/490/C
给定一个长度不超过 1 e 6 1\mathrm{e}6 1e6的整数 s s s和两个整数 a , b ( 1 ≤ a , b ≤ 1 e 8 ) a,b\ \ (1\leq a,b\leq 1\mathrm{e}8) a,b (1≤a,b≤1e8).将 s s s分为不相交的两部分,使得两部分都不包含前导零,且第一部分是 a a a的倍数,第二部分是 b b b的倍数.若无解,输出"NO";否则输出"YES"并输出任一组解.
设 s s s的长度为 n n n.求 s s s的前缀 s [ 1 ⋯ i ] s[1\cdots i] s[1⋯i]模 a a a的值 x i x_i xi和 s s s的后缀 s [ ( n − i + 1 ) ⋯ n ] s[(n-i+1)\cdots n] s[(n−i+1)⋯n]模 b b b的值 y i y_i yi,因 s s s不含前导零,故只需检查第二部分是否有前导零即可.
const int MAXN = 1e6 + 5;
char s[MAXN];
int a, b;
int x[MAXN], y[MAXN];
void solve() {
cin >> s + 1 >> a >> b;
int n = strlen(s + 1);
for (int i = 1; i <= n; i++)
x[i] = ((ll)x[i - 1] * 10 % a + s[i] - '0') % a;
int base = 1;
for (int i = n; i > 1; i--) {
y[i] = ((ll)(s[i] - '0') * base % b + (ll)y[i + 1]) % b;
base = (ll)base * 10 % b;
if (s[i] == '0') continue; // 第二部分包含前导零
if (!x[i - 1] && !y[i]) {
cout << "YES" << endl;
for (int j = 1; j <= i - 1; j++) cout << s[j];
cout << endl;
for (int j = i; j <= n; j++) cout << s[j];
return;
}
}
cout << "NO";
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/490/D
给定两块大小分别为 a 1 × b 1 a_1\times b_1 a1×b1、 a 2 × b 2 a_2\times b_2 a2×b2的矩形.现有如下两种操作:取其中一个矩形,①若该矩形可二等分,则将其二等分,保留 1 2 \dfrac{1}{2} 21;②若该矩形可三等分,则将其三等分,保留 2 3 \dfrac{2}{3} 32.问若干次操作后能否使得两矩形面积相同,若能,输出最小操作次数,并分别输出两矩形的边长;否则输出 − 1 -1 −1.
操作①等价于减少一个素因子 2 2 2;操作②等价于减少一个素因子 3 3 3,增加一个素因子 2 2 2.
求出各边长间相差的素因子 2 2 2和 3 3 3的个数,做相应数目的操作后,检查最后得到的矩形的边长之积是否相等即可.
int get(int x, int y) { // 求x中包含因子y的个数
int res = 0;
while (x % y == 0) res++, x /= y;
return res;
}
void solve() {
int a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2;
int two1 = get(a1, 2) + get(b1, 2), three1 = get(a1, 3) + get(b1, 3);
int two2 = get(a2, 2) + get(b2, 2), three2 = get(a2, 3) + get(b2, 3);
int dthree1 = max(three1 - three2, 0), dthree2 = max(three2 - three1, 0);
int dtwo1 = max(two1 + dthree1 - two2 - dthree2, 0),
dtwo2 = max(two2 + dthree2 - two1 - dthree1, 0);
int ans = dthree1 + dthree2 + dtwo1 + dtwo2;
for (int i = 0; i < dthree1; i++) {
if (a1 % 3 == 0) a1 = a1 / 3 * 2;
else b1 = b1 / 3 * 2;
}
for (int i = 0; i < dthree2; i++) {
if (a2 % 3 == 0) a2 = a2 / 3 * 2;
else b2 = b2 / 3 * 2;
}
for (int i = 0; i < dtwo1; i++) {
if (a1 % 2 == 0) a1 /= 2;
else b1 /= 2;
}
for (int i = 0; i < dtwo2; i++) {
if (a2 % 2 == 0) a2 /= 2;
else b2 /= 2;
}
if ((ll)a1 * b1 != (ll)a2 * b2) {
cout << -1;
return;
}
cout << ans << endl;
cout << a1 << ' ' << b1 << endl;
cout << a2 << ' ' << b2 << endl;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/546/D
给定两正整数 a , b ( a ≥ b ) a,b\ \ (a\geq b) a,b (a≥b),令 n = a ! b ! n=\dfrac{a!}{b!} n=b!a!.现有操作:选择一个 > 1 >1 >1的整数 x s . t . x ∣ n x\ s.t.\ x\mid n x s.t. x∣n,令 n / = x n/=x n/=x.求最大操作次数.
有 t ( 1 ≤ t ≤ 1 e 6 ) t\ \ (1\leq t\leq 1\mathrm{e}6) t (1≤t≤1e6)组测试数据.每组测试数据给定两个整数 a , b ( 1 ≤ b ≤ a ≤ 5 e 6 ) a,b\ \ (1\leq b\leq a\leq 5\mathrm{e}6) a,b (1≤b≤a≤5e6).
显然每次操作取当前 n n n的素因子即可.
预处理出 5 e 6 5\mathrm{e}6 5e6以内每个数的素因子的个数 f a c t o r s [ ] factors[] factors[],求其前缀和 p r e [ ] pre[] pre[],则每个询问 a n s = p r e [ a ] − p r e [ b ] ans=pre[a]-pre[b] ans=pre[a]−pre[b].
const int MAXN = 5e6 + 5;
int primes[MAXN], cnt;
bool state[MAXN];
int factors[MAXN]; // factors[n]表示n的素因子的个数
ll pre[MAXN]; // factors[]的前缀和
void init() {
for (int i = 2; i < MAXN; i++) {
if (!state[i]) primes[cnt++] = i, factors[i] = 1;
for (int j = 0; (ll)primes[j] * i < MAXN; j++) {
state[primes[j] * i] = true;
factors[primes[j] * i] = factors[i] + 1;
if (i % primes[j] == 0) break;
}
}
for (int i = 1; i < MAXN; i++) pre[i] = pre[i - 1] + factors[i];
}
void solve() {
int a, b; cin >> a >> b;
cout << pre[a] - pre[b] << endl;
}
int main() {
init();
CaseT // 单测时注释掉该行
solve();
}
原题指路:https://codeforces.com/problemset/problem/552/C
给定两个整数 w , m ( 2 ≤ w ≤ 1 e 9 , 1 ≤ m ≤ 1 e 9 ) w,m\ \ (2\leq w\leq 1\mathrm{e}9,1\leq m\leq 1\mathrm{e}9) w,m (2≤w≤1e9,1≤m≤1e9).问 m m m能否由 w 0 , w 1 , ⋯ , w 100 w^0,w^1,\cdots,w^{100} w0,w1,⋯,w100线性表出.
暴力模拟 m m m用 w w w表示的过程即可,时间复杂度 O ( log m ) O(\log m) O(logm).
注意判断 w 0 w^0 w0时要先判断 ( m − 1 ) (m-1) (m−1)能否被 w w w整除,再判断 ( m + 1 ) (m+1) (m+1)能否被 w w w整除,否则 m = 1 m=1 m=1时死循环.
void solve() {
int w, m; cin >> w >> m;
while (m) {
if (m % w) { // 不整除才要判
if ((m - 1) % w == 0) m--; // 注意先判m-1
else if ((m + 1) % w == 0) m++;
else {
cout << "NO";
return;
}
}
m /= w;
}
cout << "YES";
}
int main() {
solve();
}