[Codeforces] number theory (R1600) Part.9

[Codeforces] number theory (R1600) Part.9

题单:https://codeforces.com/problemset/page/1?tags=number+theory%2C1201-1600

1349A. Orac and LCM

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

题意 $(3\mathrm{s})$

给定一个长度为$n(2\le n\le 1\mathrm{e}5)$的序列$a_1,\cdots ,a_n(1\le a_i\le 2\mathrm{e}5)$.求任意两下标不同的元素的$\mathrm{lcm}$构成的集合的$\gcd$.

思路I

设素数$p$,则$p^k\mid ans$当且仅当$a[]$中至少有$(n-1)$个元素是$p^k$的倍数.

[证] (1)若$a[]$中只有$(n-2)$个$p^k$的倍数,则$\exists x,ys.t.p^k\nmid a_x,p^k\nmid a_y$,进而$p^k\nmid \mathrm{lcm}(a_x,a_y)$,则$p^k\nmid ans$.

(2)若$a[]$中至少有$(n-1)$个$p^k$的倍数,则任意两个$a_i,a_j$中至少有一个$p^k$的倍数,显然$p^k\mid ans$.

设$d_i$是$a[]$除$a_i$外的元素构成的集合,则$\gcd d_i$至少能被$(n-1)$个$a[]$中的元素整除.

若$a[]$中至少有$(n-1)$个元素是$p^k$的倍数,则$\exists is.t.p^k\mid \gcd d_i$,

​ 此时$ans=\mathrm{lcm}(\gcd (d_1),\cdots ,\gcd (d_n))$.

考察如何求$\gcd d_i$.先求前缀$\gcd$数组$pr{e}_i$和后缀$\gcd$数组$su{f}_i$,则$\gcd d_i=\gcd (pr{e}_{i-1},su{f}_{i+1})$.

代码I

const int MAXN = 1e5 + 5;
int n;
int a[MAXN];
int pre[MAXN], suf[MAXN];  // 前缀gcd、后缀gcd

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];

  for (int i = 1; i <= n; i++) pre[i] = gcd(pre[i - 1], a[i]);
  for (int i = n; i >= 1; i--) suf[i] = gcd(suf[i + 1], a[i]);

  ll ans = 1;
  for (int i = 1; i <= n; i++) 
    ans = lcm(ans, gcd(pre[i - 1], suf[i + 1]));
  cout << ans;
}

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

---

---

1350B. Orac and Models

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

题意 $(3\mathrm{s})$

有编号$1\sim n$的$n$个物品,大小分别为$s_1,\cdots ,s_n$.现要从中依次选若干个物品组成一个序列,即选中的物品编号升序.称构成的序列是好的,如果对相邻的选中物品的编号$i_j$和$i_{j+1}$,有$i_j\mid i_{j+1}$,且$s_{i_j}<s_{i_{j+1}}$.特别地,只包含一个物品的序列也是好的.求好的序列的长度的最大值.

有$t(1\le t\le 100)$组测试数据.每组测试数据第一行输入一个整数$n(1\le n\le 1\mathrm{e}5)$.第二行输入$n$个整数$s_1,\cdots ,s_n(1\le s_i\le 1\mathrm{e}9)$.数据保证所有测试数据的$n$之和不超过$1\mathrm{e}5$.

思路

$dp[i]$表示以第$i$个物品结尾的好的序列的长度的最大值,则$ans=\underset{1\le i\le n}{\max }dp[i]$.

状态转移方程$dp[i]=\underset{j\mid i,s_j<s_i}{\max }{f}_j+1$.通过枚举倍数转移时间复杂度$O(n\log n)$,通过枚举约数转移时间复杂度$O(n\sqrt{n})$.

代码

const int MAXN = 1e5 + 5;
int n;
int s[MAXN];
int dp[MAXN];  // dp[i]表示以第i个物品结尾的好的序列的长度的最大值

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    dp[i] = 1;  // 清空
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 2 * i; j <= n; j += i)
      if (s[i] < s[j]) dp[j] = max(dp[j], dp[i] + 1);
  }

  cout << *max_element(dp + 1, dp + n + 1) << endl;
}

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

---

---

1360D. Buying Shovels

原题指路:https://codeforces.com/problemset/problem/1360/D

题意 $(2\mathrm{s})$

有$t(1\le t\le 100)$组测试数据.每组测试数据输入两个整数$n,k(1\le n,k\le 1\mathrm{e}9)$.设$n$的不大于$k$的最大约数为$d$,输出$\frac{n}{d}$.

思路

①若$k\ge n$,则$ans=1$;

②若$n$是素数,则$ans=n$.

③枚举$n$的$\le \sqrt{n}$的约数$d$,检查是否有$\frac{n}{d}\le k$.

代码

bool check(int n) {  // 判断素数
  if (n <= 2) return n == 2;

  for (int i = 2; (ll)i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}

void solve() {
  int n, k; cin >> n >> k;

  if (k >= n) cout << 1 << endl;
  else if (check(n)) cout << n << endl;
  else {
    int ans = n;
    for (int i = 1; (ll)i * i <= n && i <= k; i++) {
      if (n % i == 0) {
        if (i <= k) ans = min(ans, n / i);
        if (n / i <= k) ans = min(ans, i);
      }
    }
    cout << ans << endl;
  }
}

int main() {
  CaseT  // 单测时注释掉该行
    solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

---

1370C. Number Game

原题指路:https://codeforces.com/problemset/problem/1370/C

题意 $(2\mathrm{s})$

Ashishgup和FastestFinger玩游戏,Ashishgup先手.初始时给定一个整数$n$.每轮每人需进行如下两个操作之一:①设$d$是$n$的$>1$的奇约数,令$n/=d$;②若$n>1$,令$n--$,无法操作者负.两人都采取最优策略,问谁胜.

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

思路

(1)$n$为奇数时,

​ ①若$n=1$,则Ashishgup第一步无法操作,FastestFinger胜.

​ ②若$n\ge 3$,则Ashishgup第一步令$n/=n$,则FastestFinger无法操作,Ashishgup胜.

(2)$n$为偶数且$n$无$>1$的奇约数时,显然$n$只能是$2$的幂次.

​ ①$n=2$时,Ashishgup胜.

​ ②$n\ge 4$时,Ashishgup第一步只能令$n--$使其变为$\ge 3$的奇数,此时FastestFinger胜.

(3)$n$为偶数且有奇约数时,

​ ①若$4\mid n$,则Ashishgup第一步令$n$除以其最大的奇约数使其变为$2^x(x>1)$,此时Ashishgup胜.

​ ②设$n=2p$,其中$p$为奇数.

​ i)若$p$为素数,无论Ashishgup第一步选哪个操作都会使其变为必败态,此时FastestFinger胜.

​ ii)若$p$非素数,则$p=p_1{p}_2$,其中$p_1$是素数,$p_2$是$>1$的奇数.

​ Ashishgup第一步令$n/=p_2$,此时$n=2p_1$,此时Ashishgup胜.

代码

bool check(int n) {  // 判断素数
  if (n <= 2) return n == 2;

  for (int i = 2; (ll)i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}

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

  bool ok = true;
  if (n == 1) ok = false;
  if (n % 2 == 0 && (n & (n - 1)) == 0 && n >= 4) ok = false;
  if (n % 2 == 0 && n % 4 && check(n / 2)) ok = false;

  cout << (ok ? "Ashishgup" : "FastestFinger") << endl;
}

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

---

---

1372B. Omkar and Last Class of Math

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

题意

有$t(1\le t\le 10)$组测试数据.每组测试数据输入一个整数$n(2\le n\le 1\mathrm{e}9)$.求两个正整数$a,bs.t.a+b=n$,且$\mathrm{lcm}(a,b)$最小.

思路

设$n$的最大真约数为$d$,则取$d,n-d$时$\mathrm{lcm}(d,n-d)$最小.

[证] 设最优解为$k$和$(n-k)$.不失一般性,不妨设$k\le n-k$,则$n-k\ge \frac{n}{2}$.

(1)下证:若$k\mid n$,则$\mathrm{lcm}(k,n-k)=n-k<n$.

​ 设$n=mk$,则$n-k=(m-1)k$,此时$\mathrm{lcm}(k,n-k)=n-k$.

(2)下证:若$k\nmid n$,则$\mathrm{lcm}(k,n-k)>n$.

​ 因$\mathrm{lcm}(a,b)=b$当且仅当$a\mid b$,则若$k\nmid n,(n-k)$,则$\mathrm{lcm}(k,n-k)\ne n-k$.

​ 因$\mathrm{lcm}(k,n-k)$是$(n-k)$的倍数,则$\mathrm{lcm}(k,n-k)\ge 2(n-k)\ge 2\cdot \frac{n}{2}=n$.

故为使得$\mathrm{lcm}(k,n-k)$最小,$k$应取$n$的非自身的最大约数.

代码

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

  for (int i = 2; (ll)i * i <= n; i++) {
    if (n % i == 0) {
      int ans = n / i;
      cout << ans << ' ' << n - ans << endl;
      return;
    }
  }
  cout << 1 << ' ' << n - 1 << endl;
}

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

---

---

1379B. Dubious Cyrpto

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

题意

有$t(1\le t\le 20)$组测试数据.每组测试数据输入三个整数$l,r,m(1\le l\le r\le 5\mathrm{e}5,1\le m\le 1\mathrm{e}10)$.求三个整数$a,b,c\in [l,r]s.t.na+b-c=m$,输出任一组解.数据保证有解.

思路

显然可以用$O(t(r-l))$的时间复杂度通过.

固定$b=l$或$c=r$.枚举$a$,则$c-b=m\%a$,检查答案是否在区间$[l,r]$中即可.

代码

void solve() {
  int l, r; ll m; cin >> l >> r >> m;

  for (int a = l; a <= r; a++) {
    int p = a - m % a;  // c-b
    if (l + p <= r) {
      cout << a << ' ' << l << ' ' << l + p << endl;
      return;
    }
    else if (r - p >= l) {
      cout << a << ' ' << r - p << ' ' << r << endl;
      return;
    }

    p = a - p;
    if (l + p <= r) {
      cout << a << ' ' << l + p << ' ' << l << endl;
      return;
    }
    else if (r - p >= l) {
      cout << a << ' ' << r << ' ' << r - p << endl;
      return;
    }
  }
}

int main() {
  CaseT  // 单测时注释掉该行
    solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

---

1396A. Multiples of Length

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

题意

给定一个长度为$n(1\le n\le 1\mathrm{e}5)$的序列$a_1,\cdots ,a_n(-1\mathrm{e}9\le a_i\le 1\mathrm{e}9)$.现有操作:选择$a[]$中的一个区间,区间中的每个数加上$len$的某个倍数(可不同),其中$len$为区间长度.构造三个操作,使得操作后$a[]$的所有元素变为$0$,若有多组解,输出任一组.

思路

(1)$n=1$时,操作:①$[1,1]+=0$;②$[1,1]+=0$;③$[1,1]+=-a_1$.

(2)$n\ge 2$时,操作:

​ ①$[1,1]+=-a_1$.

​ ② [ 1 , n ] + = { 0 , − n ⋅ a 2 , − n ⋅ a 3 , ⋯   , − n ⋅ a n } [1,n]+=\{0,-n\cdot a_2,-n\cdot a_3,\cdots,-n\cdot a_n\} [1,n]+={0,−n⋅a2​,−n⋅a3​,⋯,−n⋅an​}.

​ ③$[2,n]+=\{(n-1)\cdot a_2,(n-1)\cdot a_3,\cdots ,(n-1)\cdot a_n\}$.

代码

void solve() {
  int n; cin >> n;
  vi a(n);
  for (auto& ai : a) cin >> ai;

  if (n == 1) {
    cout << "1 1" << endl;
    cout << 0 << endl;
    cout << "1 1" << endl;
    cout << 0 << endl;
    cout << "1 1" << endl;
    cout << -a[0] << endl;
  }
  else {
    cout << "1 1" << endl;
    cout << -a[0] << endl;

    cout << "1 " << n << endl;
    cout << 0 << ' ';
    for (int i = 1; i < n; i++) cout << (ll)-n * a[i] << ' ';
    cout << endl;

    cout << "2 " << n << endl;
    for (int i = 1; i < n; i++) cout << (ll)(n - 1) * a[i] << ' ';
    cout << 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
24
25
26
27
28
29
30
31

---

---

1397B. Power Sequence

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

题意

称一个长度为$n$的序列$a_0,\cdots ,a_{n-1}$是好的,如果对$\forall i\in [0,n-1]$,都有$a_i=c^i$,其中$c\in {\mathbb{Z}}^{+}$.

给定一个长度为$n(3\le n\le 1e5)$的序列$a_0,\cdots ,a_{n-1}(1\le a_i\le 1\mathrm{e}9)$.现有如下两种操作:①将序列重新排序;②选一个下标$i$,令$a_i--$或$a_i++$.求将序列$a[]$变为好的序列的最小操作次数.

思路

操作①的最优策略是将$a[]$按非降序排列.

[证] 将$a_i$变为$c^i$的代价为$|a_i-c^i|$.

若存在一对$(i,j)s.t.i<j$且$a_i>a_j$,交换$a_i$和$a_j$后,由 ∣ x ∣ + ∣ y ∣ = max ⁡ { ∣ x + y ∣ , ∣ x − y ∣ } |x|+|y|=\max\{|x+y|,|x-y|\} ∣x∣+∣y∣=max{∣x+y∣,∣x−y∣}知:

∣ a i − c i ∣ + ∣ a j − c j ∣ = max ⁡ { ∣ ( a i + a j ) − ( c i + c j ) ∣ , ∣ ( a i − a j ) − ( c i − c j ) ∣ } |a_i-c^i|+|a_j-c^j|=\max\{|(a_i+a_j)-(c^i+c^j)|,|(a_i-a_j)-(c^i-c^j)|\} ∣ai​−ci∣+∣aj​−cj∣=max{∣(ai​+aj​)−(ci+cj)∣,∣(ai​−aj​)−(ci−cj)∣}

​ ≥ max ⁡ { ∣ ( a j + a i ) − ( c i + c j ) ∣ , ∣ ( a j − a i ) − ( c i − c j ) ∣ } = ∣ a j − c i ∣ + ∣ a i − c j ∣ \geq \max\{|(a_j+a_i)-(c^i+c^j)|,|(a_j-a_i)-(c^i-c^j)|\}=|a_j-c^i|+|a_i-c^j| ≥max{∣(aj​+ai​)−(ci+cj)∣,∣(aj​−ai​)−(ci−cj)∣}=∣aj​−ci∣+∣ai​−cj∣.

因$a_i>a_j$且$c^i\le c^j$,故最小步数不增,进而最优策略是将$a[]$按非降序排列.

将$a[]$按非降序排列,设$a_{max}=a_{n-1}$.将$a[]$变为好的序列所需的步数为$f(x)=\sum _{i=0}^{n-1}|a_i-x^i|$,其中$f(c)$是最小步数.

注意到$c^{n-1}-a_{max}\le f(c)\le f(1)$,则$c^{n-1}\le f(1)+a_{max}$.

遍历$x=1,2,\cdots$直至$x^{n-1}>f(1)+a_{max}$,对每个$x$线性地求$f(n)$,更新最小答案即可,总时间复杂度$O(n\cdot \max (x))$.

这样不会TLE的原因:注意到$f(1)=\sum _{i=0}^{n-1}(a_i-1)<n\cdot a_{max}\le 1\mathrm{e}9\cdot n$,

则$x^{n-1}\le f(1)+a_{max}\le 1\mathrm{e}9\cdot (n+1)$.$n=3,4,5,6$时,$\max (x)$分别不超过$63245,1709,278,93$,故可过.

注意可能爆ll,但爆ll的显然不是最优解.

代码

ll add(ll a, ll b) { return a + b < INFF ? a + b : INFF; }

ll mul(ll a, ll b) { return INFF / a > b ? a * b : INFF; }

void solve() {
  int n; cin >> n;
  vi a(n);
  for (auto& ai : a) cin >> ai;
  sort(all(a));

  ll ans = accumulate(all(a), (ll)0) - n;
  for (int x = 1;; x++) {
    ll cur = 1, res = 0;
    for (int i = 0; i < n; i++) {
      res = add(res, abs(a[i] - cur));
      cur = mul(cur, x);
    }

    if (cur == INFF || cur / x > ans + a[n - 1]) break;
    ans = min(ans, res);
  }
  cout << ans;
}

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
24
25
26
27

---

---

1401C. Mere Array

原题指路:https://codeforces.com/problemset/problem/1401/C

题意 $(2\mathrm{s})$

给定一个长度为$n$的序列$a_1,\cdots ,a_n$.现有操作:设序列最小元素为$m$.选择两个下标$i,j\in [1,n]s.t.\gcd (a_i,a_j)=m$,则交换$a_i$和$a_j$.若经若干次操作可使得$a[]$非降序,则输出"YES";否则输出"NO".

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据第一行输入一个整数$n(1\le n\le 1\mathrm{e}5)$.第二行输入$n$个整数$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}9)$.

思路

显然不是$m$的倍数的$a_i$位置不能修改.

是$m$的倍数的$a_i$间可任意交换位置.

[证] 设$a_x=m;m\mid a_y,a_z$.为交换$a_y$和$a_z$,可先交换$a_x$和$a_y$,然后交换$a_y$和$a_z$,最后交换$a_x$和$a_z$.

代码

void solve() {
  int n; cin >> n;
  vi a(n), tmpa(n);
  int m = INFF;  // a[]的最小元素
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    tmpa[i] = a[i];
    m = min(m, a[i]);
  }

  sort(all(tmpa));

  for (int i = 0; i < n; i++) {
    if (a[i] != tmpa[i] && a[i] % m) {
      cout << "NO" << endl;
      return;
    }
  }
  cout << "YES" << endl;
}

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

---

---

1407B. Big Vova

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

题意

给定一个长度为$n$的序列$a_1,\cdots ,a_n$,将其排序为序列$b_1,\cdots ,b_n$,使得序列$c_1,\cdots ,c_n$的字典序最大,其中$c_i=\underset{1\le j\le i}{\gcd }{b}_j$.若有多组解,输出任一组.

有$t(1\le t\le 1000)$组测试数据.每组测试数据第一行输入一个整数$n(1\le n\le 1000)$.第二行输入$n$个整数$a_1,\cdots ,a_n(1\le a_i\le 1000)$.数据保证所有测试数据的$n$之和不超过$1000$.

思路I

设初始时$b[]$为空,现依次将$a[]$中的元素放到$b[]$中.

设此时已放了$(k-1)$个元素,现令$b_k=a_{j}s.t.c_k=\gcd (b_1,\cdots ,b_{k-1},a_j)$最大,显然这样$c[]$的字典序最大.

事实上,解与$b_k$的具体值无关,因为每个$c_j$都整除$c_{j-1}$,则$\gcd (b_k,c_j)=\gcd (c_k,c_j)(j\ge k)$.

设有备用元素$c_0=0$,则对$\forall k\ge 1$,有$\gcd (0,k)=k$.

做$n$次操作,第$i$次操作时在$a[]$剩下的元素中选一个$a_{j}s.t.gcd(a_j,c_{i-1})$最大,令$b_i=a_j$.

第$i$次操作的时间复杂度为$O((n-i)\log A)$,其中$A=\underset{1\le i\le n}{\max }{a}_i$,总时间复杂度$O(n^2\log A)$.

代码I

void solve() {
  int n; cin >> n;
  vi a(n);
  int minidx = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] > a[minidx]) minidx = i;
  }

  vi b(n);
  b[0] = a[minidx], a[minidx] = 0;

  int cgcd = b[0];
  for (int i = 1; i < n; i++) {
    int cidx = 0, cans = 0;  // 要选择的a[j]的下标j、最大c[i]
    for (int j = 0; j < n; j++) {
      if (a[j] && gcd(a[j], cgcd) > cans) {
        cans = gcd(a[j], cgcd);
        cidx = j;
      }
    }

    b[i] = a[cidx], a[cidx] = 0;
    cgcd = cans;
  }

  for (int i = 0; i < n; i++) cout << b[i] << " \n"[i == n - 1];
}

int main() {
  CaseT  // 单测时注释掉该行
    solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

思路II

设序列$a[]$中有$cn{t}_x$个元素为$x$.用$cnt[]$,每次操作可在$O(A\log A)$的时间复杂度内找到最优的$b_k$,总时间复杂度$O(An\log A)$.

---

思路III

注意到对$\forall i>1$,要么$c_i=c_{i-1}$,要么$2c_i\le c_{i-1}$,这表明$c[]$只有$O(\log A)$种不同取值.

设当前已将$a[]$中的$k$个元素放入$b[]$中,$c_k=\gcd (b_1,\cdots ,b_k)$.

做$O(\log A)$次操作,每次操作在$a[]$剩下的元素中选一个$xs.t.\gcd (c_k,x)$最大,

​ 将$a[]$中所有值为$x$的元素放入$b[]$中.每次操作时间复杂度$O(n\log A)$,总时间复杂度$O(n{\log }^{2}A)$.

---

---