Number theory
A. Submarine in the Rybinsk Sea (easy edition)
全都写下来之后可以看到，就是把每个数字双写，全都相加，再乘以n。
所以主要就是双写，拆分成每一位，乘以11，再乘以相应十的次方。
注意精度
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
| #include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const ll mod = 998244353;
int n;
ll ans;
ll po[20];
void init() {
po[0] = 1;
for (int i = 1; i < 20; i++) {
po[i] = po[i - 1] * 10 % mod;
}
}
ll cal(ll x) {
ll tmp = 0;
int i = 0;
while (x > 0) {
int t = x % 10;
t *= 11;
tmp = (tmp + t * po[i]) % mod;
x /= 10;
i += 2;
}
return tmp;
}
int main() {
init();
cin >> n;
for (int i = 0; i < n; i++) {
ll a;
cin >> a;
ans = (ans + cal(a)) % mod;
}
ans = ans * n%mod;
cout << ans << endl;
return 0;
}
|
B. Divisor Subtraction
因为偶数除了2之外都不是质数，所以那些质数，除了2，都是奇数。
- 原数是偶数，那一定是要-2，-2，不停的减2，只要算n/2；
- 原数是奇数，那一定会有一个奇数的质数，把它减掉之后，变成了偶数，再按第一种情况不断-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
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
ll n;
ll ans;
const int maxn = 1e5 + 50;
int prime[maxn];
bool is_prime[maxn];
int sieve(int n) {
int p = 0;
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
prime[p++] = i;
for (int j = 2 * i; j <= n; j+=i) {
is_prime[j] = false;
}
}
}
return p;
}
int main() {
cin >> n;
int p = sieve((int)sqrt(n));
ll ans = 1;
for (int i = 0; i < p; i++) {
if (n%prime[i] == 0) {
n -= prime[i];
ans += n / 2;
break;
}
}
cout << ans;
return 0;
}
|
C. Line
扩展欧几里得模板题
遇到要解二元一次方程的试试欧几里得就对了。比上一场的还简单一些，对解没有限制条件。
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
| #include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
ll n;
ll x, y;
ll exgcd(ll a, ll b) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll t = exgcd(b, a%b);
ll tmp = x;
x = y;
y = tmp - (a / b)*y;
return t;
}
int main() {
ll a, b, c;
cin >> a >> b >> c;
ll g = exgcd(a, b);
if (c%g != 0)
cout << -1;
else {
x = x * (-c / g);
y = y * (-c / g);
cout << x << ' ' << y;
}
return 0;
}
|
D. The Sum of the k-th Powers
n个数的k次方和是k+1次多项式，而拉格朗日插值法告诉我们要确定k+1次多项式需要k+2个点，因此先暴力算出k+2个点，再代入公式。（计算的时候直接带着mod，mod后的结果任是k+1次多项式）
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const int maxn = 1e6 + 50;
ll y[maxn];
ll fac[maxn];
int n, k;
ll ans, tol = 1;
ll pw(ll x, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * x%mod;
}
x = x * x%mod;
p >>= 1;
}
return res;
}
ll get_fac(int x) {
if (x == 1 || x == k + 2)return fac[k + 1];
else
return fac[x - 1] * fac[k + 2 - x] % mod;
}
void init() {
y[1] = 1;
for (int i = 2; i <= k + 2; i++) {
y[i] = (y[i - 1] + pw(i, k)) % mod;
}
fac[0] = fac[1] = 1;
for (int i = 2; i <= k + 2; i++) {
fac[i] = fac[i - 1] * i%mod;
}
for (int i = 1; i <= k + 2; i++) {
tol = tol * (n - i) % mod;
}
}
int main() {
cin.sync_with_stdio(false);
cin >> n >> k;
init();
if (n <= k + 2) {
cout << y[n];
return 0;
}
for (int i = 1; i <= k + 2; i++) {
ll tmp = tol * pw(n - i, mod - 2) % mod;
tmp = tmp * pw(get_fac(i), mod - 2) % mod;
if ((k + 2 - i) % 2)
tmp *= -1;
ans = (ans + y[i] * tmp) % mod;
}
while (ans < 0) {
ans += mod;
}
cout << (ans%mod);
return 0;
}
|
H. Round Corridor
最小公倍数
上一场cf div2的比赛刚出来，第二天就拿来用了。。昨天a了，就直接把代码拿过来了。
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
49
50
51
52
53
54
55
56
57
58
| #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include <functional>
#include<string>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
ll gcd(ll a, ll b) {
if (a < b)
swap(a, b);
if (b == 0) {
return a;
}
return gcd(b, a%b);
}
ll n, m;
int q;
int main() {
cin.sync_with_stdio(false);
cin >> n >> m >> q;
ll t = gcd(m, n);
n /= t; m /= t;
while (q--) {
int sx, ex;
ll sy, ey;
cin >> sx >> sy >> ex >> ey;
sy--; ey--;
if (sx == 1 && ex == 1) {
if ((sy / n) == (ey / n))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else if (sx == 2 && ex == 2) {
if ((sy / m) == (ey / m))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else if (sx == 1 && ex == 2) {
if ((sy / n) == (ey / m))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else {
if ((sy / m) == (ey / n))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
return 0;
}
|
J. Soldier and Number Game
分解质因数加上阶乘，因为阶乘相除相当于两个区间端点，所以把各个阶乘预处理下，先因数分解，最后答案就是两阶乘减一下。
这里因数分解利用了素数筛法，一边筛素数，一边统计因子个数。
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
| #include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
#define ll long long
const int maxn = 5e6 + 5;
const int N = 5e6;
int t;
int a, b;
int num[maxn];
bool is_prime[maxn];
void init() {
memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= N; i++) {
if (is_prime[i]) {
num[i] = 1;
for (int j = 2*i; j <= N; j += i) {
int tmp = j;
while (tmp%i == 0) {
num[j]++;
tmp /= i;
}
is_prime[j] = false;
}
}
}
for (int i = 2; i <= N; i++) {
num[i] = num[i] + num[i - 1];
}
}
int main() {
init();
scanf("%d", &t);
for (int i = 0; i < t; i++) {
scanf("%d%d", &a, &b);
printf("%d\n", num[a] - num[b]);
}
return 0;
}
|
K. Complicated GCD
两个数及其之间的所有数都能有共同的因数，这基本上是不可能的，除非这两个数相等，所以判断两个数如果相等，则输出这个数，否则输出1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
#define ll long long
string a, b;
int main() {
cin >> a >> b;
if (a == b)cout << a;
else cout << 1;
return 0;
}
|
