[Codeforces] number theory (R1600) Part.10

[Codeforces] number theory (R1600) Part.10

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

1423K. Lonely Numbers

原题指路:https://codeforces.com/problemset/problem/1423/K

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

称两个相异的正整数$a,b$是朋友,如果$\gcd (a,b),\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}$可构成非退化三角形的边长.对一个由正整数构成的集合,称其中一个元素是孤独的,如果它在该集合中无朋友.给定由$[1,n]$的整数组成的集合,求其中孤独的数的个数.

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

思路

(1)素数$p$非孤独当且仅当集合中存在$p^2$,此时组成三角形的三边分别为$p,1,p$.

(2)对合数$x=p^2(p\in primes)$,因$p^2$在$[1,n]$中,则$p$也在$[1,n]$中,故它不孤独.

(3)对合数$x\ne p^2(p\in primes)$,设组成三角形的三边分别为$a,b,c(a>c)$,其中$b=\gcd (a,c)\in \left(1,\sqrt{a}\right)$.

​ 下面证明$\exists c\in \mathbb{Z}s.t.\frac{a}{b}+b>\frac{c}{b},\frac{a}{b}+\frac{c}{b}>b,\frac{c}{b}+b>\frac{a}{b}$.

​ ①因$a>c$,则$\frac{a}{b}+b>\frac{c}{b}$显然成立.

​ ②因$b<\sqrt{a}$,则$\frac{a}{b}+\frac{c}{b}>\frac{a}{b}>b$.

​ ③下证$\exists c\in \mathbb{Z}s.t.\frac{a}{b}-b<c<\frac{a}{b}$.因$b>1$,则区间长度$>1$,故区间内至少存在一个整数,故证.

综上,一个数非孤独当且仅当它是素数且它的平方不在集合中.

设$pre[i]$为$[1,i]$中素数的个数,则$ans=pre[n]-pre\left[\lfloor \sqrt{n}\rfloor \right]+1$.

代码

const int MAXN = 1e6 + 5;
int primes[MAXN], cnt;
bool state[MAXN];
int pre[MAXN];  // pre[i]表示[1,i]中素数的个数

void init() {
  state[0] = state[1] = true;

  for (int i = 2; i < MAXN; i++) {
    if (!state[i]) primes[cnt++] = i;

    for (int j = 0; primes[j] * i < MAXN; j++) {
      state[primes[j] * i] = true;
      if (i % primes[j] == 0) break;
    }
  }

  for (int i = 1; i < MAXN; i++) pre[i] = pre[i - 1] + !state[i];
}

void solve() {
  int n; cin >> n;
  cout << pre[n] - pre[(uint)sqrt(n)] + 1 << endl;
}

int main() {
  init();
  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

---

---

1444A. Division

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

题意

有$t(1\le t\le 50)$组测试数据.每组测试数据给定一对整数$p,q(1\le p\le 1\mathrm{e}18,2\le q\le 1\mathrm{e}9)$,求一个最大的$xs.t.x\mid p,q\nmid x$.

思路

$x\mid p$表示$x$的所有素因子都在$p$中出现,$q\nmid x$表示$q$存在$x$没有的素因子或$q$与$x$中同一素因子的次数前者$>$后者.

因$x\mid p$,则$x\le p$,而$q\le 1\mathrm{e}9$,先将其素因数分解,对每个素因数$i$,从$tmp=p$开始一直除以$i$直至$q\nmid tmp$,最终答案即$q$的所有素因子得到的$tmp$取$\max$.时间复杂度$O(\sqrt{p}+\log p\cdot \log q)$.

代码

vi get(int n) {  // 求n的素因子
	vi res;
	for (int i = 2; i <= n / i; i++) {
		if (n % i == 0) res.push_back(i);
		while (n % i == 0) n /= i;
	}
	
	if (n > 1) res.push_back(n);
	return res;
}

void solve() {
	ll p, q; cin >> p >> q;
	if (p % q) {
		cout << p << endl;
		return;
	}
	
	ll ans = 1;
	for (auto i : get(q)) {
		ll tmp = p;
		while (tmp % q == 0) tmp /= i;
		ans = max(ans, tmp);
	}
	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
30
31

---

---

1454D. Number into Sequence

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

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

给定一个整数$n>1$,构造一个序列$a_1,\cdots ,a_{k}s.t.\prod _{i=1}^k{a}_i=n,a_i\mid a_{i+1}(1\le i\le k-1)$,且$k$尽量大.若有多组解,输出任一组.

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

思路

设$n=\prod _{i=1}^m{p}_i^{{\alpha }_i}$,则$k\le \underset{1\le i\le m}{\min }{\alpha }_i=a_j$.取$a_1=\cdots =a_{k-1}=p_j,a_k=\frac{n}{p_j^{k-1}}$即可.

代码

vll get(ll n) {  // 求n的素因数分解
  vll res;
  for (int i = 2; (ll)i * i <= n; i++) {
    if (n % i == 0) {
      int s = 0;
      while (n % i == 0) n /= i, s++;
      res.push_back({ s,i });
    }
  }
  if (n > 1) res.push_back({ 1,n });
  return res;
}

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

  auto factors = get(n);
  sort(all(factors), greater());

  vl ans(factors[0].first, factors[0].second);
  for (int i = 1; i < factors.size(); i++)
    ans.back() *= pow(factors[i].second, factors[i].first);

  cout << ans.size() << endl;
  for (auto i : ans) cout << 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
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

---

1458A. Row GCD

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

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

给定一个长度为$n(1\le n\le 2\mathrm{e}5)$的序列$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}18)$和一个长度为$m(1\le m\le 2\mathrm{e}5)$的序列$b_1,\cdots ,b_m(1\le b_i\le 1\mathrm{e}18)$.对每个$j\in [1,m]$,求$\gcd (a_1+b_j,\cdots ,a_n+b_j)$.

思路

注意到$\gcd (a_1+b_j,\cdots ,a_n+b_j)=\gcd (a_1+b_j,a_2-a_1,\cdots ,a_n-a_1)$即可.

代码

void solve() {
  int n, m; cin >> n >> m;
  vl a(n), b(m);
  for (auto& ai : a) cin >> ai;
  for (auto& bi : b) cin >> bi;

  ll g = 0;
  for (int i = 1; i < n; i++) g = gcd(g, abs(a[i] - a[i - 1]));

  for (int i = 0; i < m; i++) cout << gcd(g, a[0] + b[i]) << ' ';
}

int main() {
  solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

---

1462D. Add to Neighbour and Remove

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

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

给定一个长度为$n$的序列$a_1,\cdots ,a_n$.现有操作,每次操作分为两步:①选择一个下标$a_i$,令$a_{i-1}+=a_i$或$a_{i+1}+=a_i$;②移除$a_i$.问至多$n$次操作后能否使得$a[]$中的元素都相等.

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

思路

因序列至多操作$(n-1)$次,可枚举操作次数$i$,则操作后剩下$(n-i)$个元素.

注意到每次操作后序列的元素之和$sum$不变,若最后所有元素等于$k$,则$sum=(n-i)k$.模拟操作过程,检查答案是否合法即可,时间复杂度$O(n^2)$.

代码

const int MAXN = 3005;
int n;
int a[MAXN];

bool check(int m, int k) {  // 判断操作后能否剩下m个k
  int sum = 0, cnt = 0;  // 当前数之和、
  for (int i = 0; i < n; i++) {
    sum += a[i];
    if (sum > k) return false;  //  不合法
    if (sum == k) cnt++, sum = 0;  // 凑出一个k
  }
  return cnt == m;
}

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

  for (int i = 0; i < n; i++) {  // 枚举操作次数
    if (sum % (n - i) == 0 && check(n - i, sum / (n - i))) {
      cout << i << 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
31
32
33
34

---

---

1487D. Pythagorean Triples

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

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

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入一个整数$n(1\le n\le 1\mathrm{e}9)$.求有多少个整数三元组$(a,b,c)s.t.1\le a\le b\le c\le n$,且$a^2+b^2=c^2,c=a^2-b$.

思路

$c^2=a^2+b^2,c=a^2-b$,两式相减得$b^2+b=c^2-c$,即$b(b+1)=c(c-1)$,则$c=b+1$.

代入得$a^2=2b+1$,即每个$>1$的奇数$a$对应唯一的一个$b$,进而对应唯一的一个$c$.枚举奇数$a$,检查对应的$c$是否不超过$n$即可,时间复杂度$O(a)\approx O\left(\sqrt{c}\right)=O\left(\sqrt{n}\right)$.

代码

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

  int ans = 0;
  for (int i = 3; (ll)i * i <= 2 * n - 1; i += 2) ans++;
  cout << ans << endl;
}

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

---

---

1505B. DMCA

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

题意

给定一个整数$n(1\le n\le 1\mathrm{e}6)$,求其digit root.

思路

设$d=n\mathrm{mod}9$,则$n$的digit root为$\{\begin{array}{l}d,d\ne 0\\ 9,d=0\end{array}$.

代码

void solve() {
  int n; cin >> n;
  cout << (n % 9 ? n % 9 : 9);
}

int main() {
  solve();
}
1
2
3
4
5
6
7
8

---

---

1514C. Product 1 Modulo N

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

题意

给定一个整数$n(2\le n\le 1\mathrm{e}5)$,在序列$[1,\cdots ,n-1]$中求一个最长的子列使得其中元素之积模$n$余$1$,升序输出该子列.

思路

乘积模$n$余$1$,则乘积可表示为一个数乘它模$n$意义下的逆元.显然不能选模$n$意义下逆元不存在或逆元不在集合中的数,而$a$在模$n$意义下不存在逆元当且仅当$\gcd (a,n)\ne 1$,故不能选与$n$不互素的数.

设所有与$n$互素的数之积在模$n$下为$prod$.

①若$prod=1$,则这些数全选即最优解.

②若$prod\ne 1$,因$\gcd (prod,n)=1$,不选值为$prod$的数即可使得乘积在模$n$下为$1$.

代码

const int MAXN = 1e5 + 5;
int n;
bool ok[MAXN];  // 记录要选的数

void solve() {
  cin >> n;
  int prod = 1;
  for (int i = 1; i < n; i++) {
    if (gcd(i, n) == 1) {
      ok[i] = true;
      prod = (ll)prod * i % n;
    }
  }

  if (prod != 1) ok[prod] = false;

  cout << count(ok + 1, ok + n + 1, 1) << endl;
  for (int i = 1; i < n; i++)
    if (ok[i]) cout << i << ' ';
}

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

---

---

1519C. Berland Regional

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

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

有编号$1\sim n$的$n$所大学.有编号$1\sim n$的$n$个学生,其中$i$号学生在$u_i$号大学,其能力值为$s_i$.现设定队伍的人数$k$,每个学校将选出能力前$k$大的人组成一支队伍,该学校的能力值为其队伍成员的能力值之和.若某学校人数不足以组成队伍,则其能力值为$0$.对每个$k\in [1,n]$,求所有大学的能力值之和.

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

思路

将每个学校的学生按能力值降序排序,维护前缀和数组$pre[i][j]$表示$i$号学校的前$j$个人的能力值之和.

设$i$号学校人数为$x_i$,则其对答案的贡献为$pre[i]\left[\lfloor \frac{x_i}{k}\rfloor \cdot k\right]$,其中只有$k\in [1,x_i]$需计算.

代码

void solve() {
  int n; cin >> n;
  vi u(n), s(n);
  for (auto& ui : u) {
    cin >> ui;
    ui--;
  }
  for (auto& si : s) cin >> si;

  vector school(n);
  for (int i = 0; i < n; i++) school[u[i]].push_back(s[i]);

  for (int i = 0; i < n; i++) sort(all(school[i]), greater());

  vector pre(n, vl(1, 0));  // pre[i][j]表示i号学校前j个同学的能力值之和
  for (int i = 0; i < n; i++) 
    for (auto j : school[i]) pre[i].push_back(pre[i].back() + j);

  vl ans(n + 1);
  for (int i = 0; i < n; i++) {
    for (int k = 1; k <= school[i].size(); k++)
      ans[k] += pre[i][school[i].size() / k * k];
  }

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

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

---

---

1521B. Nastia and a Good Array

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

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

称一个序列是好的,如果任意两相邻元素的$\gcd =1$.给定一个长度为$n$的序列$a_1,\cdots ,a_n$.现有操作:选择两不同的下标$i,j(1\le i,j\le n,i\ne j)$和两个整数 x , y   s . t .   min ⁡ { a i , a j } = min ⁡ { x , y } x,y\ s.t.\ \min\{a_i,a_j\}=\min\{x,y\} x,y s.t. min{ai​,aj​}=min{x,y},令$a_i=x,a_j=y$.用至多$n$次操作将序列变为好的序列,可以证明一定有解.

有$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)$.数据保证所有测试数据的$n$之和不超过$2\mathrm{e}5$.

思路

设$x=\underset{1\le i\le n}{\min }{a}_i=a_{pos}$.考虑构造一个以$a_{p}os$为谷底的"V字型",使得任意两相邻元素相差$1$.

对每个下标$i(1\le i\le n,i\ne pos)$,做操作$(pos,i,x,x+|pos-i|)$,显然它符合 min ⁡ { a i , a j } = min ⁡ { x , y } \min\{a_i,a_j\}=\min\{x,y\} min{ai​,aj​}=min{x,y},其效果为令$a_i=x+|pos-i|$.

代码

void solve() {
  int n; cin >> n;
  int x = INF, pos = 0;
  for (int i = 1; i <= n; i++) {
    int a; cin >> a;
    if (a < x) x = a, pos = i;
  }

  cout << (n - 1) << endl;
  for (int i = 1; i <= n; i++) {
    if (i != pos) 
      cout << pos << ' ' << i << ' ' << x << ' ' << x + abs(pos - i) << endl;
  }
}

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

---

---