codeforces 272 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

题目链接:Dreamoon and Sums

代码:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define MOD 1000000007LL

int main() {
LL a,b;
while (cin >> a >> b) {
LL s = 0LL, ss = 0LL, sum = 0LL;

s = (1+b-1)*(b-1)/2;
s %= MOD;

ss = (1+a) * a / 2;
ss %= MOD;

sum += (((s*b)%MOD)*ss)%MOD;

sum += a * s;
sum %= MOD;

cout << sum << endl;

}
return 0;
}

题目链接:Dreamoon and Sets

题意 & 题解:

如果要4个数字,两两数的gcd都是k,那么只要找出4个数字,两两数的gcd是1,每个数字再乘上k即可;所以只要解决k=1的情况即可

  • 相邻奇数的gcd是1,这个是很容易想到并证明的
  • 相邻奇数之间的那个偶数,跟那两个奇数也是互质的;这样我们就找到3个数字了
  • 有了一个偶数,不能再选偶数了,那就选一个奇数吧,就选最接近的那个,粗略想一下,是跟刚才那3个数字互质的
1
2
3
4
1 2 3 5
7 8 9 11
13 14 15 17
……………

代码:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define MAXN 10010

LL ans[MAXN][4];

int n,k;

int main() {
while (scanf("%d%d", &n, &k) != EOF) {
for (int i = 0; i < n; i++) {
ans[i][0] = 1LL+2LL*(i*3LL);
ans[i][1] = ans[i][0] + 1;
ans[i][2] = ans[i][1] + 1;
ans[i][3] = ans[i][2] + 2;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++)
ans[i][j] *= k;
}
cout << ans[n-1][3] << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
cout << ans[i][j];
if (j != 3) printf(" ");
else printf("\n");
}
}
}
return 0;
}