[Codeforces] number theory (R1200) Part.10

[Codeforces] number theory (R1200) Part.10

题单:https://codeforces.com/problemset/page/6?tags=number%20theory,0-1200

1658B. Marin and Anti-coprime Permutation

原题指路:https://codeforces.com/problemset/problem/1658/B

题意

定义一个长度为$n$的排列$p_1,\cdots ,p_n$是好的,如果$\gcd (1\cdot p_1,2\cdot p_2,\cdots ,n\cdot p_n)>1$.求$1\sim n$的排列中好的排列的个数,答案对$998244353$取模.

有$t(1\le t\le 1000)$组测试数据.每组测试数据输入一个$n(1\le n\le 1000)$.

思路

令$g=\gcd (1\cdot p_1,2\cdot p_2,\cdots ,n\cdot p_n)$,则$g\le 2$.

[证] ①$g>2$时,若$\exists$素数$p>2s.t.p\mid g$,因$1\sim n$中有$\lfloor \frac{n}{p}\rfloor$个$p$的倍数,则至多能匹配$2\lfloor \frac{n}{p}\rfloor <n$个数.

②$g\le 2$时,可将值为奇数的数放在偶数下标的位置,将值为偶数的数放在奇数下标的位置.$1\sim n$中有$\frac{n}{2}$个奇数和$\frac{n}{2}$个偶数,故$ans={\left[\left(\frac{n}{2}\right)!\right]}^2$.

代码

const int MAXN = 1005;
const int MOD = 998244353;
int fac[MAXN], ifac[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;
}

void solve() {
	init();

  CaseT {
    int n; cin >> n;
    cout << (n & 1 ? 0 : (ll)fac[n / 2] * fac[n / 2] % MOD) << endl;
  }
} 

int main() {
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

---

1679A. AvtoBus

原题指路:https://codeforces.com/problemset/problem/1679/A

题意

有A和B两种车,分别有$4$、$6$个轮子.现已知所有车的轮子总数$n$,求总车数的最小值和最大值,无解输出$-1$.

有$t(1\le t\le 1000)$组测试数据.每组测试数据第一行输入一个整数$n(1\le n\le 1\mathrm{e}18)$.

思路

设A、B两种车的数量分别为$x,y$,则$4x+6y=n$.

显然$n<4$或$n$是奇数时无解.有解时,方程转化为$2x+3y=\frac{n}{2}$.

(1)为使得总车数最小,应让$y$尽量大.

​ ①若$\frac{n}{2}\equiv 0(\mathrm{mod}3)$,显然$ans=\frac{n}{3}$.

​ ②若$\frac{n}{2}\equiv 1(\mathrm{mod}3)$,可拆成$3+\cdots +3+2+2$.

​ ③若$\frac{n}{2}\equiv 2(\mathrm{mod}3)$,可拆成$3+\cdots +3+2$.

​ 综上,$ans=\lceil \frac{n}{3}\rceil$.

(2)为使得总车数最大,应让$x$尽量大.

​ ①若$\frac{n}{2}\equiv 0(\mathrm{mod}2)$,显然$ans=\frac{n}{2}$.

​ ②若$\frac{n}{2}\equiv 1(\mathrm{mod}2)$,可拆成$2+\cdots +2+3$.

​ 综上,$ans=\lfloor \frac{n}{2}\rfloor$.

代码

void solve() {
	ll n; cin >> n;

	if (n < 4 || n & 1) {
		cout << -1 << endl;
		return;
	}
	else {
		n >>= 1;
		cout << (n + 2) / 3 << ' ' << n / 2 << endl;
	}
}

int main() {	
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

---

1712B. Woeful Permutation

原题指路:https://codeforces.com/problemset/problem/1712/B

题意

构造一个$1\sim n$的排列$p_1,\cdots ,p_{n}s.t.\mathrm{lcm}(1,p_1)+\cdots +\mathrm{lcm}(n,p_n)$最大,若有多组解,输出任一组.

有$t(1\le t\le 1000)$组测试数据.每组测试数据输入一个整数$n(1\le n\le 1\mathrm{e}5)$.数据保证所有测试数据的$n$之和不超过$1\mathrm{e}5$.

思路

最优策略:①若$n$为偶数,则偶数放奇数位,奇数放偶数位,形如$2,1,4,3,\cdots ,n,n-1$;②若$n$为奇数,则先放将$1$放在第一位,剩下的偶数个数转化为情况①,形如$1,3,2,5,4,\cdots ,n,n-1$.

[证] 定义函数 f ( x , y ) = { x y , x ≠ y x , 其余情况 f(x,y)=

f(x,y)={xy,x=yx,其余情况​.

显然$\mathrm{lcm}(x,y)\le f(x,y)$,问题转化为求$f(1,p_1)+\cdots +f(n,p_n)$的最大值.

考察问题:求$1\cdot p_1+\cdots +n\cdot p_n$的最大值,其中$p_i\ne i(1\le i\le n)$.

​ 该问题等价于求$f(1,p_1)+\cdots +f(n,p_n)$的最大值,因为若存在这样的下标$i$,可交换$p_i$和$p_j(1\le j<i)$.

以排列中的$n$个元素为节点、以$i\to p_i$为边.除$p_1=1$的情况外,其余环的边数至少为$2$.

对一个环$x_1,\cdots ,x_k$,若无$p_i$的限制,该环对最大值的贡献为$x_1^2+\cdots +x_k^2$.

$x_1^2+x_2^2+\cdots +x_k^2-(x_1{x}_2+x_2{x}_3+\cdots +x_k{x}_1)$

​ $=\frac{x_1^2}{2}-x_1{x}_2+\frac{x_2^2}{2}+\frac{x_2^2}{2}-x_2{x}_3+\frac{x_3^2}{2}+\cdots +\frac{x_k^2}{2}-x_k{x}_1+\frac{x_1^2}{2}$

​ $=\frac{(x_1-x_2{)}^2+(x_2-x_3{)}^2+\cdots +(x_k-x_1{)}^2}{2}$

​ ≥ ∣ x 1 − x 2 ∣ + ∣ x 2 − x 3 ∣ + ⋯ + ∣ x k − x 1 ∣ 2 ≥ max ⁡ { x 1 , ⋯   , x k } − min ⁡ { x 1 , ⋯   , x k } \geq \dfrac{|x_1-x_2|+|x_2-x_3|+\cdots+|x_k-x_1|}{2}\geq \max\{x_1,\cdots,x_k\}-\min\{x_1,\cdots,x_k\} ≥2∣x1​−x2​∣+∣x2​−x3​∣+⋯+∣xk​−x1​∣​≥max{x1​,⋯,xk​}−min{x1​,⋯,xk​}.

考虑如何最小化所有环的 max ⁡ { x 1 , ⋯   , x k } − min ⁡ { x 1 , ⋯   , x k } \max\{x_1,\cdots,x_k\}-\min\{x_1,\cdots,x_k\} max{x1​,⋯,xk​}−min{x1​,⋯,xk​}之和.

(1)若$n$是偶数,可将相邻两数成环,形如$(1,2),(3,4),\cdots ,(n-1,n)$,

​ 此时所有环的 max ⁡ { x 1 , ⋯   , x k } − min ⁡ { x 1 , ⋯   , x k } \max\{x_1,\cdots,x_k\}-\min\{x_1,\cdots,x_k\} max{x1​,⋯,xk​}−min{x1​,⋯,xk​}之和的最小值为$\frac{n}{2}$.

(2)若$n$是奇数,

​ ①若$p_1=1$,显然最小值为$\frac{n-1}{2}<\frac{n}{2}$,比(1)更优.

​ ②若$p_1\ne 1$,显然最小值为$\frac{n+1}{2}>\frac{n}{2}$,比(1)更劣.

综上,该构造可使得$f(1,p_1)+\cdots +f(n,p_n)$最大,进而使得$\mathrm{lcm}(1,p_1)+\cdots +\mathrm{lcm}(n,p_n)$最大.

代码

void solve() {
	int n; cin >> n;
	
	if (n & 1) {
		cout << 1 << ' ';
		for (int i = 2; i <= n; i += 2) cout << i + 1 << ' ' << i << ' ';
		cout << endl;
	}
	else {
		for (int i = 1; i <= n; i += 2) cout << i + 1 << ' ' << i << ' ';
		cout << endl;
	}
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

---

1717A. Madoka and Strange Thoughts

原题指路:https://codeforces.com/problemset/problem/1717/A

题意

给定一个正整数$n$,有多少对$(a,b)(1\le a,b\le n)s.t.\frac{\mathrm{lcm}(a,b)}{\gcd (a,b)}\le 3$.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入一个整数$n(1\le n\le 1\mathrm{e}8)$.

思路

满足要求的$(a,b)$只有三种形式:$(x,x),(x,2x),(x,3x)$.

[证] 设$d=\gcd (a,b)$.

注意到$a=kd(k>4)$是不满足要求的,因为此时$\mathrm{lcm}(a,b)\ge kd>3d$,

故可能满足要求的$(a,b)$只有四种形式:$(d,d),(d,2d),(d,3d),(2d,3d)$,

​ 而最后一种形式中$\mathrm{lcm}(a,b)=6d$,不满足要求.

注意$a,b$无序,故形如$(x,2x)$和$(x,3x)$的对数要乘$2$,$ans=n+2\left(\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{3}\rfloor \right)$.

代码

void solve() {
	int n; cin >> n;
	cout << n + 2 * (n / 2 + n / 3) << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9

---

---

1720A. Burenka Plays with Fractions

原题指路:https://codeforces.com/problemset/problem/1720/A

题意

给定两个分数$\frac{a}{b}$和$\frac{c}{d}$.现有操作:选定一个整数$x$,将一个分数的分子或分母乘$x$(分母不能乘$0$).问使得两分数相等所需的最小步数.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入四个整数$a,b,c,d(0\le a,c\le 1\mathrm{e}9,1\le b,d\le 1\mathrm{e}9)$.

思路

两次操作必可使得两分数相等,其中第一步将第一个分数乘$bc$,得到$\frac{abc}{b}=ac$,第二步将第二个分数乘$ad$,得到$\frac{acd}{d}=ac$.

若初始时两分数已相等,则$ans=0$.

下面讨论$ans=1$的情况:

①操作为将第一个分数的分子乘$x$,即$\frac{ax}{b}=\frac{c}{d}$,则$x=\frac{bc}{ad}\in \mathbb{Z}$,进而$ad\mid bc$.

②操作为将第一个分数的分母乘$x$,同理得$bc\mid ad$.

代码

void solve() {
	ll a, b, c, d; cin >> a >> b >> c >> d;
	
	ll x = a * d, y = b * c;
	if (x == y) cout << 0 << endl;
	else if (y && x % y == 0 || x && y % x == 0) cout << 1 << endl;
	else cout << 2 << endl;
}

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

---

截至2022.09.14,无新题目.