[Codeforces] number theory (R1200) Part.7

[Codeforces] number theory (R1200) Part.7

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

1389A. LCM Problem

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

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

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入两个整数$l,r(1\le l<r\le 1\mathrm{e}9)$,问是否$\exists x,y\in \mathbb{Z}s.t.l\le x<y\le r,l\le \mathrm{lcm}(x,y)\le r$,若存在,输出任一组满足的$x,y$;否则输出$-1-1$.

思路

显然最优策略是取$l$和$2l$,则有解的充要条件是:$r\ge 2l$.

代码

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

	if (r < 2 * l) cout << "-1 -1" << endl;
	else cout << l << ' ' << 2 * l << endl;
}

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

---

---

1409C. Yet Another Array Restoration

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

题意

有一个包含$n$个正整数的序列.已知其中$\exists$两元素$x,ys.t.x<y$,且将该序列升序排列后是个等差数列.给定$x,y$,构造一个 max ⁡ { a 1 , ⋯   , a n } \max\{a_1,\cdots,a_n\} max{a1​,⋯,an​}最小的满足条件的序列.

有$t(1\le t\le 100)$组测试数据.每组测试数据第一行输入三个整数$n,x,y(2\le n\le 50,1\le x<y\le 50)$.

对每组测试数据,输出一个长度为$n$的满足条件的序列$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}9)$.若有多组解,输出任一组.数据保证有解.

思路I

显然等差数列的公差$d$是$y-x$的约数.添加元素$y,y-d,y-2d,\cdots$直至够$n$个元素或下一个元素$<1$,检查$x$是否在序列中,若在则该公差符合要求.若此时仍不足$n$个元素,添加元素$y+d,y+2d,\cdots$直至够$n$个元素,更新答案即可.时间复杂度$O(n\sqrt{y-x})$.

代码I

void solve() {
	int n, x, y; cin >> n >> x >> y;

	vi ans;
	for (int d = 1; d <= y - x; d++) {
		if ((y - x) % d) continue;

		vi res;
		bool foundx = false;  // 记录x是否在序列中
		int need = n;  // 记录当前序列还差多少个元素
		int cur = y;  // 当前元素
		while (cur >= 1 && need) {
			res.push_back(cur);
			foundx |= cur == x;
			cur -= d;
			need--;
		}

		cur = y;
		while (need > 0) {  // 注意此处不能写while(need--),否则下面的!need不满足
			cur += d;
			res.push_back(cur);
			need--;
		}

		sort(all(res));
		if (!need && foundx) 
			if (ans.empty() || ans.back() > res.back()) ans = res;
	}

	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
33
34
35
36
37
38

---

思路II

枚举公差$d$,考虑直接求出首项.设首项$a_1=y-kd\ge 1$,解得$k\le \lfloor \frac{y-1}{d}\rfloor$.为保证$y$在序列中,则$y$至多是等差数列的第$n$项,则$k\le n-1$.

代码II

void solve() {
	int n, x, y; cin >> n >> x >> y;

	int diff = y - x;
	for (int d = 1; d <= diff; d++) {
		if (diff % d) continue;
		if (diff / d > n - 1) continue;

		int k = min((y - 1) / d, n - 1);
		int a1 = y - k * d;
		for (int i = 0; i < n; i++) cout << a1 + i * d << " \n"[i == n - 1];
		break;
	}
}

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

---

---

1411B. Fair Numbers

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

题意

称一个正整数是fair的,如果它能被其所有非零数码整除.

有$t(1\le t\le 1000)$组测试数据.每组测试数据输入一个整数$n(1\le n\le 1\mathrm{e}18)$.求$\ge n$的最小的一个fair的数.

思路

称一个正整数是super fair的,如果它能被$1\sim 9$这$9$个数码整除.显然super fair的数是$2520$的倍数.

显然答案不超过$\ge n$的最小的super fair的数,暴力求即可.

代码

bool check(ll x) {
	string s = to_string(x);
	for (auto ch : s)
		if (ch != '0' && x % (ch & 15)) return false;
	return true;
}

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

	for (int i = 0; i < 2520; i++) {
		if (check(n)) {
			cout << n << endl;
			return;
		}
		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

---

---

1455A. Strange Functions

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

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

对正整数$x$,定义函数$f(x)$表示将$x$的十进制表示反转并去掉前导零得到的数字,如$f(321)=123,f(120)=21$.定义函数$g(x)=\frac{x}{f(f(x))}$.给定一个正整数$n$,对$[1,n]$中的任意整数$x$,问$g(x)$有多少种不同的取值.

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

思路

注意到$x=1$是最小的使得$g(x)=1$的数,$x=10$是最小的使得$g(x)=10$的数,$x=100$是最小的使得$g(x)=100$的数,故答案即$n$的十进制表示(无前导零)的长度.

代码

void solve() {
	string s; cin >> s;
	cout << s.length() << endl;
}

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

---

---

1471A. Strange Partition

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

题意

给定一个长度为$n$的序列$a_1,\cdots ,a_n$.现有如下操作:将两相邻元素替换为它们之和,注意每次操作后序列长度$-1$.对给定的整数$x$,定义序列的值为$\sum _{i=1}^k\lceil \frac{a_i}{x}\rceil$.问经过若干次(可能为零次)操作后给定序列的值最小和最大分别能取到多少.

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

思路

注意到$\lceil \frac{a+b}{x}\rceil \le \lceil \frac{a}{x}\rceil +\lceil \frac{b}{x}\rceil$,故不做任何操作时取得最大值,做$(n-1)$次操作时取得最小值.

代码

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

	vi a(n);
	ll ans1 = 0, ans2 = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		ans1 += ceil((double)a[i] / x);
		ans2 += a[i];
	}
	ans2 = ceil((double)ans2 / x);
	cout << ans2 << ' ' << ans1 << endl;
}

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

---

---

1473B. String LCM

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

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

定义字符串$x$与正整数$a$的乘法$a\cdot x$表示将$x$重复$a$次.称字符串$a$能被字符串$b$整除,如果$\exists x\in {\mathbb{Z}}^{+}s.t.b\cdot x=a$.定义字符串$s$和$t$的LCM为能整除$s$和$t$的最短的非空字符串,记作$\mathrm{lcm}(s,t)$.可以证明若$\mathrm{lcm}(s,t)$存在,则它唯一.

有$t(1\le t\le 2000)$组测试数据.每组测试数据输入两行分别表示只包含小写英文字母的字符串$s$和$t(1\le |s|,|t|\le 20)$.

对每组测试数据,若$\mathrm{lcm}(s,t)$存在,输出$\mathrm{lcm}(s,t)$;否则输出$-1$.

思路

注意到若字符串$x$是字符串$y$的倍数,则$|x|$是$|y|$的倍数.显然若$\mathrm{lcm}(s,t)$存在,则$|\mathrm{lcm}(s,t)|=\mathrm{lcm}(|s|,|t|)$,只需检查$\frac{\mathrm{lcm}(|s|,|t|)}{|s|}\cdot s$与$\frac{\mathrm{lcm}(|s|,|t|)}{|t|}\cdot t$是否相等即可.

代码

string get(int a, string x) {
	string res;
	while (a--) res += x;
	return res;
}

void solve() {
	string s, t; cin >> s >> t;

	int n = s.length(), m = t.length();
	int d = gcd(n, m);
	cout << (get(m / d, s) == get(n / d, t) ? get(m / d, s) : "-1") << endl;
}

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

---

---

1474B. Different Divisors

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

题意

有$t(1\le t\le 3000)$组测试数据.每组测试数据输入一个整数$d(1\le d\le 1\mathrm{e}4)$,求一个最小的正整数$a$满足下列条件:①$a$至少有四个约数;②$a$的任意两约数之差$\ge d$.

思路

为使得$a$最小,显然$a$有且只有$4$个约数,此时$a$有形式$a=p^3$或$a=pq$,其中$p,q\in primes$.

①$a=p^3$时,$a$有约数$1,p,p^2,p^3$.

​ 注意到$p\ge 2$时,有$p^3-p^2>p^2-p>p-1$,只需取最小的$p\ge d+1$即可.

②$a=pq$时,$a$有约数$1,p,q,pq$.不妨设$p<q$.

​ 取最小的$p\ge d+1$和最小的$q\ge p+d$,此时$pq-q=q(p-1)\ge qd>d$.

下面证明$\nexists p^{\prime },q^{\prime }\in primess.t.p^{\prime }{q}^{\prime }<pq$.

因$p$是最小的$\ge d+1$的素数,则$p^{\prime }\ge p$,同理$q^{\prime }\ge q$.故$p^{\prime }{q}^{\prime }\ge pq$.

时间复杂度$O(gap\cdot primecheck)$,其中$gap$为相邻两素数间的距离,平均为$O(\log a)$;$primecheck$为判断是否为素数的时间复杂度.

代码

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

	vi primes;
	for (int i = d + 1;; i++) {  // 求≥d+1的最小素数p
		bool flag = true;  // 记录i是否为素数
		for (int j = 2; j * j <= i; j++) {
			if (i % j == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			primes.push_back(i);
			break;
		}
	}

	for (int i = primes.back() + d;; i++) {  // 求≥p+d的最小素数q
		bool flag = true;  // 记录i是否为素数
		for (int j = 2; j * j <= i; j++) {
			if (i % j == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			primes.push_back(i);
			break;
		}
	}

	cout << min((ll)primes[0] * primes[1], (ll)primes[0] * primes[0] * primes[0]) << 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
33
34
35
36
37
38
39

---

---

1475A. Odd Divisor

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

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

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入一个整数$n(2\le n\le 1\mathrm{e}14)$.若$n$有奇约数,输出"YES";否则输出"NO".

思路

将$n$素因数分解,则$n$有奇约数的充要条件是:$n$有奇素因子.

注意到$2$是唯一的偶素数,故$n$无奇约数的充要条件是:$n$是$2$的幂次.

代码

void solve() {
	ll n; cin >> n;
	cout << (n & (n - 1) ? "YES" : "NO") << endl;
}

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

---

---

1485A. Add and Divide

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

题意

给定两正整数$a,b$.现有如下两种操作:①$a=\lfloor \frac{a}{b}\rfloor$;②$b=b+1$.求将$a$变为$0$的最小操作次数.

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

思路

注意到$\lfloor \frac{a}{b+1}\rfloor \le \lfloor \frac{a}{b}\rfloor$,则应先用操作②,即先将$b$增大到某一值,再不断地用操作①直至$a=0$.注意特判$b<2$的情况.对$b\ge 2$的情况,至多需要$\lfloor {\log }_{2}a\rfloor \le 29$步即可使得$a=0$.

枚举用操作②的次数$i\in [0,30]$,对每个$i$,求至少需用多少次操作①,更新答案即可.

时间复杂度$O({\log }^{2}a)$.

代码

void solve() {
	ll A, B; cin >> A >> B;

	ll ans = A + 3;
	for (ll i = (B < 2 ? 2 - B : 0); i < ans; i++) {
		ll a = A, b = B + i;
		ll res = i;
		while (a) {
			a /= b;
			res++;
		}
		ans = min(ans, res);
	}
	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

---

---

1487B. Cat Cycle

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

题意

有编号$1\sim n$的$n$个点围成一圈.初始时猫A在$n$号点,猫B在$1$号点.每个时刻两猫同时移动,其中猫A逆时针移动,猫B顺时针移动.若某时刻两猫移动到同一点处,则猫B逆时针多走一步到下一个点.求第$k$个时刻时猫B所在的点的编号.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入两个整数$n,k(2\le n\le 1\mathrm{e}9,1\le k\le 1\mathrm{e}9)$.

思路

①若$n$为偶数,则不会出现两猫移动到同一点处的情况.

②若$n$为奇数,则每$\lfloor \frac{n}{2}\rfloor$个时刻猫B会多走一步.因步数要对$n$取模,不妨$k--$映射到下标从$0$开始,最后$+1$即可.

代码

void solve() {
	int n, k; cin >> n >> k;
  cout << ((k - 1) + (n & 1) * ((k - 1) / (n / 2))) % n + 1 << endl;
}

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

---

---