2021牛客寒假算法基础集训营1的补题记录
I题 限制不互素对的排列
链接：https://ac.nowcoder.com/acm/contest/9981/I
来源：牛客网
题目描述
输入一个数 n ，请构造一个长度为 n 的排列，使得其中正好有 k 对相邻的数gcd（最大公约数）大于 1 。
排列是指 1 到 n 一共 n 个数，每个数都出现过且仅出现过 1 次。例如，{1, 3, 2, 5, 4}是一个排列，而 {1, 3, 5, 4, 3}、 {1, 2, } 则不是排列
输入描述:
两个整数 n 和 k ，用空格隔开。
2 <= n <= 100000, 0 <= k <= n / 2
输出描述:
如果不存在可行的构造方案，输出-1。
否则输出一行 n 数，用空格隔开。如果有多组可行的构造方案，输出任意一组即可。
示例1
输入
输出
说明
1
| 长度为2的排列有2个：{1,2}和{2,1}，显然都不符合题意
|
示例2
输入
输出
说明
1
2
| 共有3对相邻数不互素：{3,6}、{6,2}和{2,4}。
这并不是唯一解，只要构造任意合法解即可。
|
思路:
由题中给的一个很重要的信息可知，k<=n/2的，而且我们可以轻易地知道对于所有的偶数，他们的最大公因数是2满足大于1的条件，并且n以内偶数的个数正好也是n/2个。所以可以比较轻易的凑够n/2-1对儿满足条件的数对儿。这就是k<=n/2-1的方法。
对于k = n/2的情况，我们只需将6放到n/2个偶数的最后一个即可，然后后面放一个3来保证出现第n/2对儿。
代码：
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
| #include<bits/stdc++.h>
using namespace std;
int n, k;
void work1() {
for (int i=1;i<=k+1;++i) cout << i * 2 << ' ';
for (int i=k*2+3;i<=n;++i) cout << i << ' ';
for (int i=1;i<=k+1;++i) cout << 2 * i - 1 << ' ';
}
void work2() {
if (n < 6) {
cout << -1;
return;
}
for (int i=4;i<=k;++i) cout << i * 2 << ' ';
cout << 2 << ' ' << 4 << ' ' << 6 << ' ' << 3 << ' ';
cout << 1;
for (int i=k*2+1;i<=n;++i) cout << i << ' ';
for (int i=3;i<=k;++i) cout << 2 * i - 1 << ' ';
}
int main() {
cin >> n >> k;
if (k <= n / 2 - 1) work1();
else work2();
return 0;
}
|
J.一群小青蛙呱蹦呱蹦呱
链接：https://ac.nowcoder.com/acm/contest/9981/J
来源：牛客网
题目描述：
有n个格子，每个格子里有一个数，1,2,3,4…n
牛牛放出无穷只青蛙。
第一只青蛙的路线是：1->2->4->8->16->…
第二只青蛙的路线是：1->3->9->27->81->…
第三只青蛙的路线是：1->5->25->125…
第四只青蛙的路线是：1->7->49…
。。。。。。
用数学语言描述，第 只青蛙的路线是首项为1，公比为的等比数列，其中代表第个素数。
当青蛙跳到一个格子上，如果这个格子上面有一个数，青蛙就会把这个数吃掉。
牛牛想知道，所有没有被吃掉的数的lcm（最小公倍数 ，Least common multiple）是多少？
由于这个lcm可能非常大，请输出它对 1 0 9 + 7 10^9+710
9
+7 取模的值。
输入描述:
一个正整数
输出描述:
如果所有数都被吃掉了，请输出一个字符串”empty”
否则输出所有没有被吃掉的数的lcm，对 1 0 9 + 7 10^9+710 9+7 取模
示例1:
输入
输出
说明
1
2
3
4
5
6
7
8
| 数字 1 可以被所有青蛙吃掉；
数字 2 可以被第 1 只青蛙吃掉；
数字 3 可以被第 2 只青蛙吃掉；
数字 4 可以被第 1 只青蛙吃掉；
数字 5 可以被第 3 只青蛙吃掉；
数字 6 无法被吃掉；
数字 7 可以被第 4 只青蛙吃掉。
所以剩下的数字只有一个 6 ，所有数的 lcm 为 6
|
示例2:
输入
输出
思路：
性质一：由题可知按照顺序划掉的是每一个素数的几次方，所以很明显的是最后留下来的数一定是由两个以上的素数相乘得到的。
性质二：我们可以知道lcm是指两个数的最小公倍数，所以最后的答案一定是这些剩下的数字的质因数的某次方中最高那一个互相相乘的答案。
性质三：我们可以知道一个数进行质因数分解的结果应该是唯一的。
所以解法来了，先求出n / 2以内的质因数，然后对于2来说，找到log2(n/3)即为2的次方数。对于大于2小于n / 2的所有质数pi来说，logpi(n/2) 就是pi的次方数，然后将这些数都乘到一起就可以得到答案的lcm了。
知识点复习：
线性筛素数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| ll prime[maxn], size = 0;
bool vis[maxn];
void Prime() {
memset(vis, true, sizeof(vis));
memset(prime, 0, sizeof(prime));
vis[1] = true;
for (int i=2;i<=n;++i) {
if (vis[i]) prime[++size] = i;
for (int j=1;j<=size&&i*prime[j]<=n;++j) {
vis[i * prime[j]] = false;
if (i % prime[j] == 0) break;
}
}
}
|
快速幂：
1
2
3
4
5
6
7
8
| ll power(ll a, ll b) {
ll res = 1 % mod;
for (; b; b >>= 1) {
if (b & 1) res = ll(res * a % mod);
a = ll(a * a % mod);
}
return res;
}
|
代码：
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
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 8e7;
const int mod = 1e9 + 7;
ll n, ans = 1;
ll prime[maxn / 10], size = 0;
bool vis[maxn];
void Prime() {
memset(vis, true, sizeof(vis));
memset(prime, 0, sizeof(prime));
vis[1] = true;
int t = maxn;
for (int i=2;i<=t;++i) {
if (vis[i]) prime[++size] = i;
for (int j=1;j<=size&&i*prime[j]<=t;++j) {
vis[i * prime[j]] = false;
if (i % prime[j] == 0) break;
}
}
}
ll power(ll a, ll b) {
ll res = 1 % mod;
for (; b; b >>= 1) {
if (b & 1) res = ll(res * a % mod);
a = ll(a * a % mod);
}
return res;
}
int main() {
Prime();
cin >> n;
if (n < 6) {
cout << "empty";
return 0;
}
ll tmp = n / 3, c = 0;
while(tmp >= 2) tmp /= 2, c++;
ans = (ans * power(2, c) % mod) % mod;
for (int i=2;i<=size;++i) {
if(prime[i] > n / 2) break;
tmp = n / 2, c = 0;
while(tmp >= prime[i]) tmp /= prime[i], c++;
ans = (ans * power(prime[i], c) % mod) % mod;
}
cout << ans % mod;
return 0;
}
|
